Коды на одно сочетание

N п/п	k = 2	k = 3

В таком множестве кодовых комбинаций, каждая из которых состоит из n элементов, количество элементов с характерным признаком k для всех кодовых комбинаций разрешенного множества одно и то же (количество единиц в кодовой комбинации). В этом случае объем разрешенного множества определяется сочетанием из n элементов по k.

N_p = C = (15)

Максимальное количество кодовых комбинаций разрешенное множество N_p будет иметь при следующих условиях, если n четно, то k необходимо принять k= ; если n нечетно, то k= или k= .

Например, определить максимальное количество кодовых комбинаций разрешенного множества при числе элементов кодовых комбинаций равное 5, т.е. при n= 5 определить k и N_p.

k= = =2; k= =3;

N_p=C = =10; N_p=C = =10.

Как видно, при вычислении k по первому и второму способу объем разрешенной выборки кодового множества не меняется.

Разрешенное множество кодовых комбинаций с обнаружением ошибок с применением кодов на одно сочетание строится следующим образом:

строится множество двоичных кодов на все сочетания N=2ⁿ, из всего множества выбираются только те кодовые комбинации, для которых характерный признак k один и тот же.

В рассмотренном выше примере таким характерным признаком является наличие постоянного числа единиц в разрешенных кодовых комбинациях (k=2; k=3). Это множество приведено в таблице 5. Анализ кодовых комбинаций на одно сочетание показал, что для них минимальное кодовое расстояние d_min=2. В этих кодах возможно обнаружение одной и более ошибок, т.к. искажения в кодовых комбинациях приводят к изменению характерного признака конкретного кодового множества. Так для случаев k=2 и k=3 появление в кодовых комбинациях соответствующих искажений (1®0, 0®1) приводит к изменению числа единиц в разрешенных кодовых комбинациях, что и будет говорить о наличии искажений.

Избыточность кодов на одно сочетание определится из соотношения

R = 1 - = 1 - (16)

Из таблицы 4.6 следует:

R = 1 - » 0,35, d = 2, t = 1.

Другой разновидностью корректирующих кодов с обнаружением искажений являются коды с четным или нечетным числом единиц. При формировании двоичных кодовых множеств с четным (нечетным) числом единиц из всего 2ⁿ множества выбирают соответствующие кодовые комбинации, полученное разрешенное множество будет содержать N_p= =2^n-1 кодовых комбинаций, т.к. минимальное кодовое расстояние равно d=2, то такие коды способны обнаруживать одиночные искажения т.к. t = d_min - 1 = 1. Последнее равенство справедливо при условии, если в неискаженных разрешенных комбинациях число единиц четное (нечетное), и изменение одного из элементов кодовой комбинации приводит к нарушению четности (нечетности), что и позволяет судить о возникшем искажении.

Избыточность таких кодов определится как R=1- =1 - =

= при n = 4 избыточность составляет R = 0,25, т.е. коды с четным или нечетным числом единиц обладают меньшей избыточностью по сравнению с кодами на одно сочетание, а, следовательно, при одном и том же числе кодовых элементов можно получить большее количество кодовых комбинаций для кодирования исходного сообщения.

Коды с повторением также являются разновидностью корректирующих кодов с обнаружением ошибок. Эти коды строятся из исходного кода путем его дополнения аналогичной кодовой комбинацией (т.е. происходит повторение передаваемой кодовой комбинации дважды).

Например: исходная комбинация 0101, передаваемая двоичная комбинация имеет вид 01010101. Кодовая комбинация, принимаемая приемным декодирующим устройством, считается достоверной, если в дополненной кодовой комбинации исходня часть совпадает с дополненной. Избыточность таких кодов равна:

R = 1 - = 1 - = 0,5.

Коды с удвоением элементов. Эти коды также принадлежат ко множеству корректирующих кодов с обнаружением искажений, они образуются в результате удвоения каждого элемента исходной кодовой комбинации, причем нуль в исходной комбинации заменяется на два элемента 01, а единица на 10. Например, исходная кодовая комбинация имеет вид 0101, удвоенная (передаваемая по линии связи) 01100110. В передаваемых кодовых комбинациях парные соседние элементы имеют только два вида 01 или 10 и появление парных элементов в принимаемых кодовых комбинациях вида 00 или 11 будет говорить о возникших искажениях. Сформированные таким образом кодовые комбинации имеют в два раза больше элементов чем исходные, следовательно, они обладают большей избыточностью. Избыточность таких кодов определится как

R = 1 - = 1 - = 0,5.

Большой класс корректирующих кодов составляет множество систематических кодов, которые определены как блочные разделимые n, k - коды. В таких кодах, состоящих из n символьных элементов, k элементов являются информационными, а оставшиеся r=n-k элементов кодовых комбинаций проверочными. Проверочные элементы образуются с помощью линейных преобразований информационных кодовых комбинаций [6].

Как правило, систематические коды (n, k - коды) структурно составляются таким образом, что первое подмножество кодовой комбинации состоит из информационных элементов, а следующее за ним подмножество элементов кода состоит из проверочных элементов.

Построение кодовых комбинаций блочных разделимых кодов базируется на двух леммах:

1. Суммирование по модулю 2 любого множества разрешенных комбинаций также дает разрешенную комбинацию.

2. Минимальное кодовое расстояние систематического кода равно минимальному весу его ненулевых кодовых комбинаций (весом кодовой комбинации называется число единиц этой кодовой комбинации).

Кодовые комбинации называются линейно независимыми, если соблюдается следующее условие c₁f₁ c₂f₂ ... с_kf_k 0 для всех возможных значений c_i (c_i=1 Ú 0). Исключение составляет случай, когда с₁ = с₂ =... = с_к = 0.

Для образования полного множества линейно независимых кодовых комбинаций, согласно первому постулату, путем сложения по модулю 2 k линейно независимых комбинаций f₁, f₂,..., f_k и придания значений 0 или 1 коэффициентам с_i получают N_p = 2^k разрешенных кодовых комбинаций систематического кода. Определенные для построения множества комбинаций систематического кода линейно независимые комбинации f₁, f₂,..., f_k записываются друг под другом в виде матрицы G_n,k.

Такая матрица, состоящая из k строк и n столбцов, называется производящей матрицей n, k кода [7].

G_n,k = (17)

Производящая матрица представлена двумя подматрицами: информационной (a_ik) и проверочной (b_ir). Информационная матрица состоит из k столбцов, проверочная из r столбцов. В качестве информационной подматрицы производящей матрицы можно взять единичную матрицу E_k

1 0... 0

01... 0

E_,k =........… (18)

0 0... 1

С учетом (17) и (18) производящая матрица для построения систематического кода будет иметь следующий вид:

1 0... 0 b₁₁ b₁₂... b_1r

0 1... 0 b₂₁ b₂₂... b_2r

G_n,k =.................................... (19)

0 0... 1 b_k1 b_k2... b_kr

…………………….

a₁a₂... a_k b₁ b₂.... b_r

Проверочная подматрица строится на основе информационной подматрицы с учетом следующих положений. Так как каждая строка кодового множества информационной подматрицы (18) содержит только одну 1, то вес каждой строки проверочной подматрицы должен быть не менее p₁ = d_min - 1, сумма двух любых строк по модулю 2 не менее p₁₂ = d_min -2.

Алгоритм построения систематического кода определяется следующим образом:

Цель процесса алгоритмизации построить код исправляющий одиночные искажения (S=1) при числе разрешенных комбинаций (в качестве примера) N_p = 2⁵ = 32 и числе информационных элементов k = 5.

1. Определение минимального кодового расстояния

d_min = 2S + 1 = 2·1 + 1 = 3.

2. Определение общего количества элементов кодовых комбинаций систематического кода - n.

N_p = =

где: С - количество вариантов состояний кодовых комбинаций, когда искажение отсутствует (C = 1).

С - количество вариантов кодовых комбинаций, когда возникают одиночные искажения (в рассматриваемом примере C = =n.

3. Из формулы для определения N_p определяют общее количество элементов систематического кода

2^k = ; 2⁵ = ; 32 =

при определении n выбирают минимальный верхний предел, т.е. sup n sup n = 9, т.к. 32 должно быть меньше или равно , то выбирая наименьший верхний предел, получают n=9, т.е. n=9; k=5.

4. Определение числа проверочных элементов систематического кода r = n - k = 9 - 5 = 4. Для случая r=4 строится множество кодовых комбинаций N_r = {0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000,!001, 1010, 1011, 1100, 1101, 1110, 1111}. Из полученного множества для построения проверочной подматрицы производящей матрицы выбирают пять (к=5) комбинаций (любых), вес каждой из которых p d_min-1=3-1=2. Такое подмножество определится как N₅={0011, 0101, 0110, 0111, 1001}, общее же количество комбинаций, удовлетворяющих условию p 2 имеет вид N_{p 2} = {0011, 0101, 0110,0111, 1001, 1010, 1011, 1100, 1101, 1110, 1111}, т.е. N_{p 2}=12.

5. Построение производящей матрицы систематического кода- G_9,5

(20) G9,5 = 01000

Из общего количества разрешенных комбинаций систематического кода, содержащего 5 информационных символов N_р=2⁵ =32, пять комбинаций уже определено, т.к. они входят в состав производящей матрицы G_9,5, шестая комбинация нулевая (все элементы равны 0), осталось найти 26 производных комбинаций, которые определяются на основе суммирования по модулю 2 строк производящей матрицы, т.е. осуществляется кодирование систематического кода.

Для определения r поверочных элементов по известным информационным элементам необходимо построить проверочную матрицу, состоящую из r строк и n столбцов.

Проверочная матрица строится на основе единичной матрицы путем приписывания к ней слева подматрицы D_k,r, содержащей k столбцов и r строк. Каждая строка подматрицы D_k,r соответствует столбцу поверочной подматрицы производящей матрицы G_n,k

b11 b21... bk1

(21) Dk,r= b12 b22... bk2

....................

b1r b2r... bkr

Таким образом, проверочная матрица будет иметь вид

b11 b21 ... bk1 10... 0

(22)     b12 b22 ... bk2 01... 0

................................

b1r b2r... bkr 00... 1

На основании проверочной матрицы H_n,r (22) формируется алгоритм кодирования и декодирования систематического кода.

В качестве примера построим на основании производящей матрицы (20) проверочную матрицу H_9,4.

		a1	a2	a3	a4	a5		b1	b2	b3	b4
(23)
H9,4	=

По полученной проверочной матрице H_9,4 определяются проверочные элементы b₁, b₂, b₃, b₄ на основании следующих уравнений:

b₁ = a₅

b₂ = a₂ Å a₃ Å a₄

(24)

b₃ = a₁ Å a₃ Å a₄

b₄ = a₁ Å a₂ Å a₄ Å a₅

Следовательно, любая кодовая комбинация систематического кода определяется из N_p=2^k исходных комбинаций. Например, если на вход кодирующего устройства поступает исходная информационная кодовая комбинация 11001, то на его выходе образуется разрешенная кодовая комбинация систематического кода

a₁=1; a₂=1; a₃=0; a₄=0; a₅=1.

b₁=1; b₂=1; b₃=1; b₄=1.

11001 ® 11001 1111.

При исходной комбинации 10101 кодовая комбинация систематического кода определится как

a₁=1; a₂=0; a₃=1; a₄=0; a₅=1.

b₁=1; b₂=1; b₃=0; b₄=0.

10101 ® 10101 1100.

При декодировании принятых комбинаций, т.е. обработки систематического кода приемным устройством, алгоритм распознавания искаженной кодовой комбинации определяется в соответствии со следующими уравнениями:

b =b₁ Å a₅

(25)

b =b₂ Å a₂ Å a₃ Å a₄

b =b₃ Å a₁ Å a₃ Å a₄

b =b₄ Å a₁ Å a₂ Å a₄ Å a₅

Например, при передаче разрешенной комбинации 110011111 произошло искажение в пятом разряде и принята комбинация 1100 0 1111 (искажение в 5 разряде, передана 1, а принят 0).

Если при проверке приемным устройством разрешенной комбинации систематического кода окажется, что хотя бы одно из уравнений (25) не будет равно 0, то в кодовой комбинации произошли ошибки. В приведенном примере принятая кодовая комбинация 1100 0 1111 по уравнениям (25) при a₁=1, a₂=1, a₃=0, a₄=0, a₅=0, b₁=1, b₂=1, b₃=1, b₄=1 оценивается как:

b =1 Å 0 =1

(26)

b =1 Å 1 Å 0 Å 0=0

b =1 Å 1 Å 0 Å 0=0

b =1 Å 1 Å 1 Å 0 Å 0=0

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

Если же предусмотрена операция исправлений искажений, то необходимо провести дальнейший анализ уравнений (25).

Так, например, наличие 1 в первом и четвертом уравнениях говорит о том, что искаженным может быть один из элементов разрешенной кодовой комбинации систематического кода b₁, b₄, a₁, a₂, a₄, a₅.

Наличие 0 во втором и третьем уравнениях означает, что элементы b₂, b₃, a₁, a₂, a₃, a₄ приняты без искажений. Исключая правильно принятые элементы из первого и четвертого уравнений определяют потенциально искаженные элементы. Таким искаженным элементом в рассматриваемом примере может быть один из b₁, b₄, a₅, но элемент a₅ входит и в первое и во второе уравнения, следовательно, искажен он.

Заменив в принятой кодовой комбинации в элементе 5 значение 0 на 1, восстанавливается искаженная кодовая комбинация. Результаты проверок правильности принятых кодовых комбинаций по уравнениям (25) называют синдромом (синдром-определитель), так же называется и программно-аппаратный модуль приемного устройства.

7.1.2.1. Код Хэмминга. Особенностью кода Хэмминга является то обстоятельство, что столбцы проверочной матрицы располагаются таким образом, что r -комбинация i- столбца соответствовала бы номеру i кодовой комбинации, записанному в двоичной форме. Такое расположение столбцов позволяет построить синдром таким образом, что его номер в двоичной форме будет указывать на номер искаженного элемента принятой кодовой комбинации. В качестве примера рассматривается проверочная матрица H_9,4 (23). По уравнениям (25) определяются синдромы одиночных искажений, их для наглядности удобно представить в виде таблицы 4.7 (на примере 10 элементной кодовой комбинации).

Таблица 4.7