Порождающая матрица линейного блочного кода
Итеративный код
Еще одна простая схема кодирования, которая также часто используется, может быть построена следующим образом.
Предположим, что нужно передать, к примеру, девять информационных символов m = ( m0 , m1 , ..., m8 ). Эти символы можно расположить в виде квадратной матрицы, как это показано в табл. 3.1, и добавить к каждой строке и каждому столбцу этой таблицы по проверочному символу (проверка на четность).
Таблица 3.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 |
Таким образом, по строкам и по столбцам этой таблицы будет выполняться правило четности единиц.
Если в процессе передачи по каналу с помехами в этой таблице произойдет одна ошибка (например в символе m4), то проверка на четность в соответствующей строке и столбце (в нашем примере - P2 и P5) не будет выполняться.
Иными словами, координаты ошибки однозначно определяются номерами столбца и строки, в которых не выполняются проверки на четность. Таким образом, этот код, используя различные проверки на четность (по строкам и по столбцам), способен не только обнаруживать, но и исправлять ошибки (если известны координаты ошибки, то ее исправление состоит просто в замене символа на противоположный: если 0, то на 1, если 1 – то на 0 ).
Описанный метод кодирования, называемый итеративным, оказывается полезным в случае, когда данные естественным образом формируются в виде массивов, например, на шинах ЭВМ, в памяти, имеющей табличную структуру, и т.д. При этом размер таблицы в принципе не имеет значения (3х3 или 20х20), однако в первом случае будет исправляться одна ошибка на 3х3=9 символов, а во втором – на 20х20=400 символов.
Обратим внимание еще на один момент. Если в простом коде с проверкой на четность для обнаружения ошибки приходится добавлять к информационной последовательности всего один символ, то для того, чтобы код стал исправлять однократную ошибку, понадобилось к девяти информационным символам добавить еще семь проверочных.
Таким образом, избыточность этого кода оказалась очень большой, а исправляющая способность – сравнительно низкой. Поэтому усилия специалистов в области помехоустойчивого кодирования всегда были направлены на поиск таких кодов и методов кодирования, которые при минимальной избыточности обеспечивали бы максимальную исправляющую способность.
Только что в качестве примера были рассмотрены два простейших корректирующих кода - код с простой проверкой на четность, позволяющий обнаруживать однократную ошибку в принятой последовательности, и блочный итеративный код, исправляющий одну ошибку с помощью набора проверок на четность по строкам и столбцам таблицы. Однако формальное правило, по которому осуществляется кодирование, то есть преобразование информационной последовательности в кодовое слово, по-настоящему еще не определено. Так как же задаются блочные коды?
Простейшим способом описания, или задания, корректирующих кодов является табличный способ, при котором каждой информационной последовательности просто назначается кодовое слово из таблицы кода (табл. 3.2)
Таблица 3.2
| m | U |
Такой способ описания кодов, кстати, применим для любых, а не только линейных кодов. Однако при больших k размер кодовой таблицы оказывается слишком большим, чтобы им пользоваться на практике (для кода с простой проверкой на четность двухбайтового слова размер таблицы составит ~ 25 * 216 = 2000000 двоичных символов).
Другим способом задания линейных блочных кодов является использование так называемой системы проверочных уравнений, определяющих правило, по которому символы информационной последовательности преобразуются в кодовые символы. Для того же примера система проверочных уравнений будет выглядеть следующим образом:
U0 = m0,
U1 = m1, (3.9)
U2 = m2,
U3 = m0 + m1 + m2.
Однако наиболее удобным и наглядным способом описания линейных блочных кодов является их задание с использованием порождающей матрицы, являющейся компактной формой представления системы проверочных уравнений:
| 1 0 0 … 0 | P00 P01 . . . . P0, n- k- 1 | ||
| G = | 0 1 0 … 0 | P10 P11 . . . . P1, n- k- 1 | |
| ……… | ……………… | . (3.10) | |
| 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 = (m0 , m1 ,. . . , mk -1) будет тем блоком-сообщением, который необходимо закодировать с использованием данного кода.
Тогда соответствующим ему кодовым словом U будет
U = m× G . (3.11)
С учетом структуры матрицы G символы кодового слова U будут такими:
для i = 0, 1, 2,. . . , k- 1
Ui = mi ; (3.12)
для i = k, k+1,. . . , n
Ui = m0× P0j + m1× P1j + m2× P2j +…+ mk- 1× Pk- 1, j . (3.13)
Иными словами, k крайних левых символов кодового слова совпадает с символами кодируемой информационной последовательности, а остальные (n - к) символов являются линейными комбинациями символов информационной последовательности.
Определенный таким образом код называется линейным блочным систематическим (n,k)-кодом с обобщенными проверками на четность, а задающая его матрица Gназывается порождающей матрицей кода.
В качестве примера рассмотрим известный (7,4)-код Хемминга, являющийся классической иллюстрацией простейших кодов с исправлением ошибок.
Пусть m = (m0, m1, m2, m3) будет тем сообщением, или информационной последовательностью, которую нужно закодировать.
Порождающая матрица G для (7. 4)-кода Хемминга имеет вид
| G(7,4) = | . | |||||||
| (3.14) | ||||||||
Тогда символы соответствующего кодового слова определяются следующим образом :
| U = m× G = ( m0 m1 m2 m3 ) | = | |||||||
= (m0 , m1 , m2 , m3 , m0 + m2 + m3 , m0 + m1 + m2 , m1 + m2 + m3 ), (3.15)
или
U0 = m0 ,
U1 = m1 ,
U2 = m2 ,
U3 = m3 , (3.16)
U4 = m0 + m2 + m3 ,
U5 = m0 + m1 + m2 ,
U6 = m1 + m2 + m3 .
Например, пусть 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 ).
Интересно отметить, что в соответствии с приведенным выше определением строки матрицы G сами являются кодовыми словами данного кода, а все остальные кодовые слова - линейными комбинациями строк порождающей матрицы.
На основании порождающей матрицы G(7,4) (3.15) или приведенной системы проверочных уравнений (3.16) легко реализовать схему кодирования для рассматриваемого (7,4)-кода Хемминга (рис. 3.4).
Кодер работает точно так же, как и при простой проверке на четность, но теперь выполняет не одну общую, а несколько частичных проверок, формируя, соответственно, несколько проверочных символов.
Рис. 3.4