Итеративный код

Еще одна простая и часто используемая схема кодирования может быть построена следующим образом.

Предположим, что нужно передать девять информационных символов m = ( m₀ , m₁ , ..., m₈ ).Эти символы можно расположить в виде квадратной матрицы ( табл. 1), и добавить к каждой строке и каждому столбцу этой таблицы по проверочному символу (проверка на четность).

Таблица 1

m0	m1	m2	P1 = m0 +m1 +m2
m3	m4	m5	P2 = m3 +m4 +m5
m6	m7	m8	P3 = m6 + m7 + m8
m0 +m3 +m6	m1+ m4 +m7	m2 +m5 +m8	m0 + m0 + m1 + m1 +…. + m8 + m8

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

Если в процессе передачи по каналу с помехами в этой таблице произойдет одна ошибка (например в символе m₄), то проверка на четность в соответствующей строке и столбце (в нашем примере - P₂ и P₅) не будет выполняться.

Иными словами, координаты ошибки однозначно определяются номерами столбца и строки, в которых не выполняются проверки на четность. Этот код способен не только обнаруживать, но и исправлять ошибки (если известны координаты ошибки, то ее исправление состоит просто в замене символа на противоположный: 0 на 1, или 1 на 0 ).

Описанный метод кодирования, называемый итеративным, оказывается полезным в случае, когда данные естественным образом формируются в виде массивов, например, на шинах ЭВМ, в памяти, имеющей табличную структуру, и т.д. При этом размер таблицы не имеет значения (3х3 или 20х20.

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

Напомним основные понятия двоичной арифметики.

Полем называется множество математических объектов, которые можно складывать, вычитать, умножать и делить.

Для простейшего поля, состоящего из двух элементов − нуля - 0 и единицы - 1 операции сложения и умножения определяются следующим образом:

0+0=0, 0× 0=0; 0+1=1, 0× 1=0; 1+0=1, 1× 0=0; 1+1=0, 1× 1=1.

Определенные таким образом операции сложения и умножения называются сложением и умножением по модулю 2 ( mod2 ) (обратите внимание, что из равенства 1+1 = 0 следует, что -1 = 1 и, соответственно, 1+1=1-1, а из равенства 1×1=1 − что 1:1=1).

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

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

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

Таблица 1

m	U
000	0000
001	0011
010	0101
011	0110
100	1001
101	1010
110	1100
111	1111

(В этом примере - Последний символ в U – сумма предыдущих трех)

Такой способ описания кодов применим для любых кодов, но при больших k размер кодовой таблицы оказывается слишком большим для использования на практике.

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

U₀ = m₀, U₁ = m₁, U₂ = m₂, U₃ = m₀ + m₁ + m₂.

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

	1 0 0 … 0	P00 P01 . . . . P0, n- k- 1
G =	0 1 0 … 0	P10 P11 . . . . P1, n- k- 1
	………	………………
	0 0 0 … 1	Pk- 1, 0 Pk- 1, 1 . . . . Pk- 1, n- k- 1
	единичная матрица I k*k	матрица Р k*(n- k)

Линейный блочный систематический (n,k)-код полностью определяется матрицей G размера k * n с двоичными матричными элементами. При этом каждое кодовое слово является линейной комбинацией строк матрицы G, а каждая линейная комбинация строк G - кодовым словом.

Пусть m = (m₀ , m₁ ,. . . , m_{k -1}) будет тем блоком-сообщением, который необходимо закодировать с использованием данного кода.

Тогда соответствующим ему кодовым словом U будет

U = m× G .

С учетом структуры матрицы G символы кодового слова U будут такими:

для i = 0, 1, 2,. . . , k- 1 U_i = m_i ; (1.12)

для i = k, k+1,. . . , n U_i = m₀× P_0j + m₁× P_1j + m₂× P_2j +…+ m_{k- 1}× P_{k- 1, j}. (1.13)

Иными словами, k крайних левых символов кодового слова совпадает с символами кодируемой информационной последовательности, а остальные (n - к) символов являются линейными комбинациями символов информационной последовательности.

Определенный таким образом код называется линейным блочным систематическим (n,k) - кодом с обобщенными проверками на четность, а задающая его матрица G называется порождающей матрицей кода.

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

Пусть m = (m₀, m₁, m₂, m₃) будет тем сообщением, или информационной последовательностью, которую нужно закодировать.

Порождающая матрица G для (7. 4)-кода Хемминга имеет вид

	1	0	0	0	1	1	0
G(7,4) =	0	1	0	0	0	1	1
	0	0	1	0	1	1	1
	0	0	0	1	1	0	1

Тогда символы соответствующего кодового слова определяются следующим образом :

	1	0	0	0	1	1	0
U = m× G = ( m0 m1 m2 m3 )	0	1	0	0	0	1	1	=
	0	0	1	0	1	1	1
	0	0	0	1	1	0	1

= (m₀ , m₁ , m₂ , m₃ , m₀ + m₂ + m₃ , m₀ + m₁ + m₂ , m₁ + m₂ + m₃ ), (1.15)

Например, для m = ( 1 0 1 1 ) соответствующее кодовое слово будет иметь вид U = ( 1 0 1 1 1 0 0 ), для m = ( 1 0 0 0 ) - U = ( 1 0 0 0 1 1 0 ).