Некоторые понятия теории кодирования

Систематический код - код, включающий кроме m информационных k контрольных разрядов. При этом возникает избыточность (абсолютная и относительная). Абсолютная избыточность равна k, а относительная определяется соотношением k/n, где n=m+k – общее количество разрядов в кодовом слове (m – число информационных разрядов).

Корректирующая способность кода определяется вероятностью обнаружения или исправления ошибки. Если вероятность искажения одного символа n-разрядного слова равна p, то вероятность искажения k символов по теореме умножения вероятностей будет ω=ρ^k(1-ρ)^n-k.

Число кодовых комбинаций, каждая из которых содержит k искаженных элементов, равна числу сочетаний из n по k:

.

Тогда полная вероятность искажения информации

.

Корректирующая способность кода связана также с понятием кодового расстояния.

Кодовое расстояние d(A,B) для кодовых комбинаций A и B определяется как вес такой третьей кодовой комбинации, которая является их суммой по модулю 2.

Вес кодовой комбинации V(A) – количество единиц, содержащихся в кодовой комбинации.

В теории кодирования [5] показано, что систематический код обладает способностью обнаружить ошибки только тогда, когда минимальное кодовое расстояние для него больше или равно 2t:

d_min≥2t,

где t – кратность обнаруживаемых ошибок.

Это означает, что между соседними разрешенными кодовыми словами должно существовать по крайней мере одно кодовое слово.

В случае если необходимо не только обнаруживать, но и исправлять ошибку (указать место ошибки), минимальное кодовое расстояние должно быть d_min≥ 2t+1.

 

Обнаружение и исправление одиночных ошибок путем использования дополнительных разрядов

Рассмотрим возможность использования дополнительных (контрольных) разрядов для обнаружения и исправления ошибок. Эта возможность заключается в том, что к n информационным разрядам добавляется один контрольный разряд. В него записывается 0 или 1 таким образом, чтобы для каждого из передаваемых чисел сумма разрядов по модулю 2 была бы равна 0 (кодирование по методу четности) или 1 (нечетности).Появление ошибки в числе обнаружится по нарушению четности или нечетности. При этом виде кодирования допускается возможность выявления только одиночной ошибки. Чтобы одна комбинация разрядов числа превратилась в другую без выявления ошибки, необходимо изменение четного (2, 4, 6 и так далее) числа разрядов одновременно. Пример реализации метода контроля по методу четности-нечетности приведен в табл. 5.

Рассмотренный способ контроля по методу четности-нечетности может быть видоизменен для локализации (выявления места) ошибки в числе. Длинное число разбивается на группы разрядов, каждая из которых содержит k разрядов.

Таблица 5

	Число	Контрольный разряд	Проверка (нечетности)
			1-ошибка

Контрольные разряды выделяются всем группам по строкам и по столбцам согласно следующей схеме:

	a1	a2	a3	a4	a5	k1
	a6	a7	a8	a9	a10	k2
	a11	a12	a13	a14	a15	k3
	a16	a17	a18	a19	a20	k4
	a21	a22	a23	a24	a25	k5
	k6	k7	k8	k9	k10

Если ошибка произошла в разряде a_s (единица изменилась на ноль или наоборот), то при проверке на четность (нечетность) сумма по i-й строке и j-му столбцу (на пересечении которых находится элемент a_s) изменится. Следовательно, можно зафиксировать нарушение четности (нечетности) по этой строке и столбцу. Это не только позволит обнаружить ошибку, но и локализовать ее место. Изменив значение разряда a_s на противоположное, можно исправить возникшую ошибку.

Контроль по методу четности-нечетности используется для контроля записи и считывания информации, а также для выполнения арифметических операций.

Коды Хемминга

Американский ученый Р. Хемминг предложил способ кодирования информации, позволяющий не только обнаруживать, но и исправлять ошибки при передаче одиночного слова любой разрядности. Эти коды – систематические. Пусть разрядность слова равна m. Для контроля информации требуется k дополнительных разрядов. Число k выбирается согласно следующим правилам.

1. Контролирующее число k выбирается так, чтобы оно имело количество комбинаций, достаточное для распознавания одной из m+k позиций или для сигнализации отсутствия ошибки. Полученное таким образом число описывает n=m+k+1 событий. Следовательно, необходимо, чтобы выполнялось неравенство 2^k≥(m+n+1).

2. (m+k)-разрядные позиции нумеруются от единицы до (m+k), начиная от младшей значащей. Контрольные разряды k обозначаются P₀, P₁, P₂, …,P_k-1 и помещаются в разряды, имеющие номера 1,2,4,8, …,2^k-1 (m+k)-разрядного числа. Остальные m разрядов могут быть размещены в любом порядке между контрольными разрядами.

3. Контрольные разряды P₀, P₁, P₂, …,P_k-1 выбраны таким образом, чтобы для определенных разрядов слова служить в качестве контрольных избыточных разрядов.

Проверка

Проверяемые разряды

…

…

…

…

…

.

.

.

P₀ выбрано с таким расчетом, чтобы в позициях 1, 3, 5, 7, 9, 11 … число единиц каждого слова было четным, P₁ выбрано для того, чтобы выполнялось условие четности в разрядах 2, 3, 6, 7, 10, 11, 14, 15 …, аналогично P₂ контролирует позиции 4,5,6,7,12,13,14,15,20… и P_{3 −} для разрядов 8, 9,10,11,12,13, 14,15,24,25….

На основании рассмотренных правил в табл. 6 показаны семиразрядные коды. Контрольные разряды обозначены P₀, P₁ и P₂ и помещены в позициях 1, 2 и 4.

Операция обнаружения и исправления ошибок выполняется путем нахождения k-разрядного контрольного числа. При этом младший значащий разряд контрольного числа находится посредством проведения контроля на четность над разрядами 1,3,5,7,9…. Если контроль показывает правильность передачи, то пишется нуль, иначе − единица. Следующий разряд контрольного числа

Таблица 6

		Разряды
	Число
		A	B	C	P2	D	P1	P0

определяется путем проверки на четность разрядов 2,3,7,10,11,14,15,…. Остальные разряды контрольного числа находятся аналогично.

Если контрольное число равно нулю, то это означает, что при передаче информации ошибка не произошла. Если же контрольное число не равно нулю, то оно указывает на тот разряд числа, где зафиксирована ошибка, которую необходимо исправить.

Пусть, например, передается число шесть 0110011, а принимается в виде 0110111, то есть произошла ошибка в третьем разряде. Выполняя контроль на четность с помощью разрядов P₀, P₁ и P₂, находим:

Контрольное число

P₀ (1, 3, 5, 7) = (1, 1, 1, 0) нечетность 1

P₁ (2, 3, 6, 7) = (1, 1, 1, 0) нечетность 1

P₂ (4, 5, 6, 7) = (0, 1, 1, 0) четность 0

Полученное контрольное число равно 011, что соответствует ошибке в третьем разряде.

Таким образом, дополнительный разряд P_i выбран так, чтобы проверять четность той совокупности разрядных позиций, чьи контрольные числа содержат единицу в позиции 2ⁱ.