Кодирование и декодирование групповых кодов

Согласно теореме Шеннона для дискретных каналов с шумами скорость передачи информации может быть сколь угодно близкойк пропускной способности канала при сколь угодно малой вероятности ошибки. При этом не накладывается каких-либо ограничений на способ кодирования передаваемой информации и длину используемого кода.

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

В современной теории кодирования широко используются основные понятия высшей алгебры: множества, матрицы, векторные пространства, группы, кольца и поля [1,2,8,9]. Групповые коды образуют особый класс кодов, построение которых производится по определенным правилам, известным из теории множеств. Из класса групповых ходов в дальнейшем будут рассматриваться только двоичные коды.

Групповым () кодом называется такой код, кодовые слова которого содержат  символов; причем символов, расположенных в определенных местах каждого кодового слова, являются информационными, а остальные () являются проверочными (избыточными). Кодовые слова группового кода образуют группу относительно некоторой математической операции (оператора группы). Если оператор группы является линейным, то групповой код также является линейным; проверочные символы такого кода образуются в результате линейных операций с информационными символами. В случае двоичных кодов эти линейные операции сводятся к операции сложения по модулю два. Кроме того, линейный код является систематическим, если последовательность информационных символов кода не изменяется в процессе кодирования.

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

Порядок группы равен , то есть равен числу кодовых слов в группе (числу элементов множества). Если для передачи информации используется k разрядов из общего числа , то количество кодовых слов в таком коде равно  (подмножество группы  порядка 2 ⁿ). При этом подмножество группы  называется подгруппой, если оно само по себе образует группу относительно операции сложения по модулю 2. В подгруппу обязательно входит нулевое слово, все кодовые символы которого равны нулю (нулевой член множества ).Например, группа , имеющая порядок  содержит в себе всё подгруппы всех других порядков от  до .Подгруппа состоит только из одного кодового слова вида 0000, а подгруппа есть сама группа , состоящая из 16 кодовых слов.

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

Так как разрешенные кодовые слова группового линейного кода образуют подгруппу относительно операции сложения по модулю 2, то для определения всех кодовых слов подгруппы достаточно найти  линейно-независимых кодовых слов (сумма этих слов по модулю 2 не должна равняться нулю). Остальные  кодовых слов (кроме нулевого слова) находятся сложением по модулю 2 во всевозможных сочетаниях этих известных кодовых слов, так как                  (1.26)

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

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

Проверочная матрица строится для определения алгоритма кодирования и декодирования данного группового кода. Каноническая форма проверочной матрицы записывается путем дополнения k столбцов к единичной матрице r ´ r (дополнение приписывается слева от единичной матрицы)

 

 

ПРИМЕР. Построить линейный код n = 7, обеспечивающий исправление одиночных ошибок.

Решение задачи:

Для исправления одиночной ошибки необходимо кодовое расстояние

d ³ 2 t _и + 1 = 3.

Можно показать, что минимально-необходимое число проверочных разрядов при данном кодовом расстоянии определяется из следующего соотношения

      2 ^r ³ 1+ C ¹ ₇ = 8, то есть r ³ 3.

Строим производящую матрицу, для чего берём квадратную единичную матрицу из k = (n – r) строк и столбцов и путём перебора добавляем проверочные разряды так, чтобы расстояние между кодовыми словами было не меньше d. Четыре строки матрицы образуют 4 кодовых слова искомого кода.

 

	1000 011 0100 110 0010 101 0001 111	1 2 3 4
1Å2	1100 101	5
1Å3	1010 110	6
1Å4	1001 100	7
2Å3	0110 011	8
2Å4	0101 001	9
3Å4	0011 010	10
1Å2Å3	1110 000	11
2Å3Å4	0111 100	12
1Å3Å4	1011 011	13
1Å2Å4	1101 010	14
1Å2Å3Å4	1111 111	15

(1.30)

Остальные 11 кодовых слов из общего числа 2 ^k - 1 находятся суммированием по модулю 2 всевозможных сочетаний строк матрицы. Нулевое слово 0000 000 обычно не используется, хотя и принадлежит данному коду (принадлежит к выбранной подгруппе группы G ₇).

Составим таблицу расстояний d_ij между кодовыми словами полученного кода.

 

 

Таблица 16 -  Расстояния d_ij

 

i j	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15	0	4 0	4 4 0     dij	3 3 3 0	3 3 3 4 0	3 3 3 3 4 0	4 3 4 3 3 3 0	3 3 3 4 4 4 7 0	4 4 3 3 3 7 4 3 0	4 3 4 3 7 3 4 3 4 0	4 4 4 7 3 3 4 3 4 4 0	7 3 3 4 4 4 3 4 3 3 3 0	3 7 3 4 4 4 3 4 3 3 3 4 0	3 3 7 4 4 4 3 4 3 3 3 4 4 0	44 4 3 3 3 4 3 4 4 4 3 3 3 0

 

Как видно из таблицы, кодовое расстояние данного кода равно трём (d =3), то есть такой код способен исправить любые одиночные ошибки.

Используя вычисленные кодовые слова, запишем проверочную матрицу:

                                                                             _{1 2 3 4 5 6 7}

                                         

Для проверочной матрицы выбраны такие кодовые слова из (1.30), проверочные символы которых образуют единичную матрицу, а число единиц является чётным; следовательно, все строки проверочной матрицы удовлетворяют проверкам на чётность

 

a ₂ Å a ₃ Å a ₄ Å a ₅ = 0,

                  a ₁ Å a ₂ Å a ₄ Å a ₆ = 0,

                  a ₁Å a ₃ Å a ₄ Å a ₇ = 0.                                                     (1.31)

 

Полученное уравнение определяет правило проверки всех комбинаций данного кода в процессе их декодирования в приёмнике. Операция кодирования в передатчике, т.е. вычисление проверочных кодовых элементов определяется алгоритмом

a ₅ = a ₂ Å a ₃ Å a _4,

a ₆ = a ₁ Å a ₂ Å a _4,

a ₇ = a ₁ Å a ₃ Å a _4.                                                                                                 (1.32)

Если от источника сообщений в кодирующее устройство поступает последовательность вида 0110, то кодирующее устройство выдаёт комбинацию вида 0110011 в соответствии с записанным выше алгоритмом.

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

a ₂ Å a ₃ Å a ₄ Å a ₅ = 1 Å 0 Å 0 Å 0 = 1,

a ₁ Å a ₂ Å a ₄ Å a ₆ = 0Å 1 Å 0 Å 1 = 0,                           

a ₁ Å a ₃ Å a ₄ Å a ₇ = 0Å 0 Å 0 Å 1 = 1.                                       (1.33)

Наличие единиц в процессе проверок указывает на искажение кодового слова, а результаты проверок являются элементами синдрома ошибки S (1,0,1).

Синдромом последовательности кодовых символов (синдромом ошибки) называется последовательность S, определяемая матричным равенством  

S = z × H ^T,                                                                          (1.34)

где H ^T- транспонированная проверочная матрица кода.

Учитывая, что z = a + e - декодируемая кодовая последовательность,          e - последовательность ошибок, a × H ^T = 0.

S = z × H ^T=(a + e) H ^T = e × H ^T.                                             (1.35)

Если необходимо исправить ошибку, анализ элементов синдрома продолжается. На основании второй проверки делается заключение, что символы a ₁, a ₂, a ₄, a ₆ не искажены. Следовательно, искажённым является один из символов: a ₃, a ₅, a ₇ (код позволяет исправить только одиночную ошибку). Так как символ a ₃ входит и в первое, и во второе уравнения, то искажён именно он. Этот символ в принятом кодовом слове заменяется на противоположный. Получается кодовое слово 0110011, совпадающее с переданным.

Рассмотренный пример позволяет построить обобщенную структурную схему декодера линейного кода, показанную на Рисунок 52.

Наиболее сложным устройством декодера, определяющим возможность его реализации, является анализатор синдрома. Синдромы ошибок используемых на практике корректирующих кодов могут содержать десятки и сотни элементов, что затрудняет реализацию устройств логического анализа системы проверочных уравнений (1.33). Число логических операций, необходимое для декодирования кодового слова длиной n (сложность декодера), обычно экспоненциально увеличивается с ростом n. Поэтому усилия разработчиков, в основном, направлены на поиск таких корректирующих кодов и таких методов декодирования, которые упрощали бы процедуру анализа синдрома ошибки. 

Существенное упрощение процедуры декодирования достигается при использовании кодов Хэмминга и циклических кодов.

 

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

Кодами Хэмминга обычно называют групповые кода:

· с кодовым расстоянием , исправляющие одиночные ошибки;

· с кодовым расстоянием , исправляющие одиночные и обнаруживающие тройные ошибки.

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

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

Кроме этого общего требования, для кодов Хэмминга является обязательным, чтобы результат проверок на четность при декодировании искаженного кодового слова указывал также номер разряда, в котором расположен искаженный символ. Этот номер представляется числом, которое образуется при записи результатов 1-ой, 2-ой,... -ой проверок в двоичной системе счисления ().

Обозначим разряды кодового слова кода Хэмминга в виде последовательности , , ,... , ... , где I, 2, 3,... k...,  - натуральные числа, представляющие собой номера разрядов. Следовательно, первая проверка должна охватывать те нечётные символы, при записи номеров которых в двоичной системе счисления обязательно имеется единица в первом разряде двоичного числа, то есть , , , , и так далее;

.

Вторая и последующие проверки строятся следующим образом

 

,

,

.                                    (1.36)

Проверочные символы располагаются в тех разрядах, которые участвуют только в одной проверке. Такими разрядами являются 1-ый 2, 4, 8, 16 и так далее.

Необходимое число проверочных разрядов в кодовом слове определяется выражением (1.29), которое для кодов Хэмминга () удобнее использовать в виде

ПРИМЕР. Необходимо закодировать кодом Хэмминга ()комбинацию из пяти информационных символов 10011.

Определяем необходимое число проверочных разрядов: 2⁵£ 2ⁿ/ n откуда . Принимаем , .

Проверочные символыы должны занять I, 2, 4 и 8 разряды кода, а информационные 3(1), 5(0), 6(0), 7(1) и 9(1) разряды (в скобках указаны значения символов). Определяем значения проверочных символов согласно уравнениям (1.36):

 

,

,

,

.

Таким образом, передаваемое кодовое слово кода Хэмминга имеет вид 101100111.

Пусть в канале связи символ, находящийся в 5-ом разряде, был искажен и кодовое слово приняло вид 101110111. В приемнике в процессе декодирования производятся проверки согласно уравнениям (1.36):

 

,

,

,

.

Записываем результат проверки в виде , что равно десятичному числу 5, которое указывает номер искаженного разряда. Следовательно, в 5-ом разряде необходимо изменить 1 на 0.

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

 

5.Вопросы:

 

1. Типы дискретного канала.

2. Классификация корректирующих кодов.

3. Коды с чётным числом единиц.

4. Коды с постоянным весом.

5. Инверсный код.

6. Коды Хэмминга.

 

Литература

1. Бабич Н. П., Жуков И. А. Компьютерная схемотехника. Методы построения и проектирования: Учебное пособие. – К.: «МК-Пресс», 2004

2. Жмакин А. П. Архитектура ЭВМ. - СПб.: БХВ-Петербург, 2006

3. Лысиков Б.Г. Цифровая и вычислительная техника.- Мн.: УП Экоперспектива, 2002

4. Новиков Ю. В. Основы цифровой схемотехники. Базовые элементы и схемы. Методы проектирования. М.: Мир, 2001

5. Угрюмов Е.П. Цифровая схемотехника.- СПб.: БХВ-Петербург, 2004

6. Бойко В. И. Схемотехника электронных схем. Микропроцессоры и микроконтроллеры. - СПб.: БХВ-Петербург, 2004

7. Цилькер Б. Я., Орлов С.А. Организация ЭВМ и систем. – СПб.: Питер, 2004