Число контрольных символов в зависимости от числа информационных разрядов для исправления одной ошибки

k

m

Число искажённых кодовых комбинаций зависит от кратности искажения и в общем случае определяется по формуле

, (4.4)

где n – число разрядов полной кодовой комбинации,

l – кратность искажения.

Неравенство (4.3) в общем случае записывается в виде

2 ^m ≥ Е+1, (4.5)

где величина Е определяется (4.4).

Формулы (4.4) и (4.5) позволяют определить число контрольных разрядов для искажений произвольной кратности.

2. Размещение контрольных символов. Для удобства обнаружения искаженного символа целесообразно размещать их на местах, кратных степени 2, т.е. на позициях 1, 2, 4, 8 и т.д. Информационные символы располагаются на оставшихся местах. Поэтому, например, для семиэлементной полной кодовой комбинации можно записать

m ₁, m ₂, k ₄, m ₃, k ₃, k ₂, k ₁, (4.6)

где k ₄ – старший (четвертый) разряд информационной кодовой комбинации двоичного кода, подлежащий кодированию; k ₁ – младший (первый) разряд.

3. Определение состава контрольных символов. Какой из символов должен стоять на контрольной позиции (1 или 0), выявляют с помощью проверочной таблицы. Рассмотрим это на примере комбинации (4.6).

Вначале составляется предварительная таблица (табл. 4.14), в которой записаны все кодовые комбинации (исключая нулевую) для трехразрядного двоичного кода на все сочетания и в правом столбце сверху вниз проставлены символы комбинации кода Хэмминга, записанные в последовательности (4.6).

Таблица 4.14

Пример предварительной таблицы кода Хэмминга

Разряды двоичных чисел	Символы кода
3(k 3)	2(k 2)	1(k 1)
			m 1
			m 2
			k 4
			m 3
			k 5
			k 2
			k 1

По предварительной таблице составляется проверочная таблица, в которой выписаны символы кодовой комбинации (4.6) в трех строках, формируемые по следующим правилам.

В первую строку записываются символы, против которых проставлены единицы в младшем (первом) разряде комбинации двоичного кода табл. 4.12. Так, в комбинациях 001, 011, 101 и 111 единицы находятся в младших разрядах, поэтому в первой строке проверочной таблицы (см. табл. 4.14) записывается символ т ₁,против которого стоит единица в комбинации двоичных чисел 001. Далее в первую строку записывается символы k ₄, k ₃ и k _1.

Во вторую строку проверочной таблицы записываются символы, против которых проставлены единицы во втором разряде двоичного кода. Так, комбинации 010, 011, 110 и 111 содержат во втором разряде 1, поэтому вторая строка проверочных коэффициентов состоит из символов m ₂, k ₃, k ₂и k ₁.

В третью строку записываются символы, против которых проставлены единицы в третьем разряде двоичного кода, это символы т ₃, k ₃, k ₂ и k ₁.

Таблица 4.15

Проверочная таблица кода Хэмминга

m 1	k 4	k 3	k 1
m2	k 4	k 2	k 1
m 3	k 3	k 2	k 1

Число строк в проверочной табл. 4.15 равно числу контрольных символов т.

В случае кодирования более длинных информационных кодовых комбинаций табл. 4.14 и 4.15 должны быть расширены, так как должны быть записаны четвертая, пятая и т.д. строки проверочных коэффициентов. Для этого нужно лишь увеличить число разрядов двоичного кода в табл. 4.14. Например, для комбинации т ₁, m ₂, k ₁₁, m ₃, k ₁₀, k ₉, k ₈, m ₄, k ₇, k ₆, k ₅, k ₄, k ₃, k ₂, k ₁,имеющей одиннадцать информационных символов и четыре контрольных символа, табл. 4.14 будет содержать 15 строк, а табл. 4.15 будет состоять из четырёх строк.

Состав контрольных символов с помощью проверок определяют следующим образом. Суммируют информационные символы, входящие в каждую строку табл. 4.15; если сумма единиц в данной строке четная, то значение символа т,входящего в эту строку, равно 0, если нечетная, то 1. По первой строке табл. 4.15 определяют значение символа т ₁,по второй – т ₂,по третьей – m ₃.

Полученные по табл. 4.15 контрольные символы подставляют в полную кодовую комбинацию (4.6) кода Хэмминга, которая теперь полностью определена.

Дата добавления: 2014-01-20