Кодирование и декодирование групповых кодов
Групповые коды
Согласно теореме Шеннона для дискретных каналов с шумами скорость передачи информации может быть сколь угодно близкойк пропускной способности канала при сколь угодно малой вероятности ошибки. При этом не накладывается каких-либо ограничений на способ кодирования передаваемой информации и длину используемого кода.
Для построения кодов с хорошими характеристиками, которые обеспечивали бы малую вероятность ошибки на выходе канала связи при заданной избыточности, требуется очень большой набор кодовых слов, то есть кодовые слова такого кода должны содержать большое число кодовых символовn. При этом значельно усложняется анализ кода, а также процедура кодирования и декодирования. Например, если , то число возможныхкодовых слов двоичного кода и декодирующее устройство приемника должно помнить кодовых слов. Возникает необходимость строить коды по определенным правилам, позволяющим осуществить достаточно просто операции кодирования и декодирования применяемого корректирующего кода.
В современной теории кодирования широко используются основные понятия высшей алгебры: множества, матрицы, векторные пространства, группы, кольца и поля [1,2,8,9]. Групповые коды образуют особый класс кодов, построение которых производится по определенным правилам, известным из теории множеств. Из класса групповых ходов в дальнейшем будут рассматриваться только двоичные коды.
Групповым()кодом называется такой код, кодовые слова которого содержат символов; причем символов, расположенных в определенных местах каждого кодового слова, являются информационными, а остальные ( ) являются проверочными (избыточными). Кодовые слова группового кода образуют группу относительно некоторой математической операции (оператора группы). Если оператор группы является линейным, то групповой код также является линейным; проверочные символы такого кода образуются в результате линейных операций с информационными символами. В случае двоичных кодов эти линейные операции сводятся к операции сложения по модулю два. Кроме того, линейный код является систематическим, если последовательность информационных символов кода не изменяется в процессе кодирования.
Таким образом, групповым линейным кодом является код, кодовые слова которого образуют подгруппу конечной группы . Конечной группой в данном случае называется множество кодовых слов, отличающееся тем свойством, что при сложении пары кодовых слов данного множества по модулю два образуется кодовые слова этого же множества, то есть, если и , то и .
Порядок группы равен , то есть равен числу кодовых слов в группе (числу элементов множества). Если для передачи информации используется k разрядов из общего числа , то количество кодовых слов в таком коде равно (подмножество группы порядка 2n). При этом подмножество группы называется подгруппой, если оно само по себе образует группу относительно операции сложения по модулю 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³ 2tи+ 1 = 3.
Можно показать, что минимально-необходимое число проверочных разрядов при данном кодовом расстоянии определяется из следующего соотношения
2r³ 1+ C17 = 8, то есть r³ 3.
Строим производящую матрицу, для чего берём квадратную единичную матрицу из k = (n– r) строк и столбцов и путём перебора добавляем проверочные разряды так, чтобы расстояние между кодовыми словами было не меньше d. Четыре строки матрицы образуют 4 кодовых слова искомого кода.
| 1000 011 0100 110 0010 101 0001 111 | ||
| 1Å2 | 1100 101 | |
| 1Å3 | 1010 110 | |
| 1Å4 | 1001 100 | |
| 2Å3 | 0110 011 | |
| 2Å4 | 0101 001 | |
| 3Å4 | 0011 010 | |
| 1Å2Å3 | 1110 000 | |
| 2Å3Å4 | 0111 100 | |
| 1Å3Å4 | 1011 011 | |
| 1Å2Å4 | 1101 010 | |
| 1Å2Å3Å4 | 1111 111 |
(1.30)
Остальные 11 кодовых слов из общего числа 2k - 1 находятся суммированием по модулю 2 всевозможных сочетаний строк матрицы. Нулевое слово 0000 000 обычно не используется, хотя и принадлежит данному коду (принадлежит к выбранной подгруппе группы G7).
Составим таблицу расстояний dij между кодовыми словами полученного кода.
Таблица 16 - Расстояния dij
| i j | |||||||||||||||
| dij |
Как видно из таблицы, кодовое расстояние данного кода равно трём (d=3), то есть такой код способен исправить любые одиночные ошибки.
Используя вычисленные кодовые слова, запишем проверочную матрицу:
1 2 3 4 5 6 7
Для проверочной матрицы выбраны такие кодовые слова из (1.30 ), проверочные символы которых образуют единичную матрицу, а число единиц является чётным; следовательно, все строки проверочной матрицы удовлетворяют проверкам на чётность
a2 Åa3 Åa4 Åa5 = 0,
a1 Åa2 Åa4 Åa6 = 0,
a1Åa3 Åa4 Åa7 = 0. (1.31)
Полученное уравнение определяет правило проверки всех комбинаций данного кода в процессе их декодирования в приёмнике. Операция кодирования в передатчике, т.е. вычисление проверочных кодовых элементов определяется алгоритмом
a5 =a2 Åa3 Åa4,
a6 =a1 Åa2 Åa4,
a7 = a1 Åa3 Åa4. (1.32)
Если от источника сообщений в кодирующее устройство поступает последовательность вида 0110, то кодирующее устройство выдаёт комбинацию вида 0110011 в соответствии с записанным выше алгоритмом.
Допустим, что в канале связи комбинация была искажена и приняла вид 0100011. Декодирующее устройство осуществляет проверки на чётность в соответствии с уравнениями
a2 Åa3 Åa4 Åa5 = 1 Å 0 Å 0 Å 0 = 1,
a1 Åa2 Åa4 Åa6 = 0Å 1 Å 0 Å 1 = 0,
a1 Åa3 Åa4 Åa7 = 0Å 0 Å 0 Å 1 = 1. (1.33)
Наличие единиц в процессе проверок указывает на искажение кодового слова, а результаты проверок являются элементами синдрома ошибки S(1,0,1).
Синдромом последовательности кодовых символов (синдромом ошибки) называется последовательность S, определяемая матричным равенством
S= z×HT , (1.34 )
где HT- транспонированная проверочная матрица кода.
Учитывая, что z=a+ e- декодируемая кодовая последовательность, e- последовательность ошибок, a×HT = 0.
S= z×HT=( a + e)HT = e×HT. (1.35)
Если необходимо исправить ошибку, анализ элементов синдрома продолжается. На основании второй проверки делается заключение, что символы a1, a2, a4, a6 не искажены. Следовательно, искажённым является один из символов: a3, a5, a7 (код позволяет исправить только одиночную ошибку). Так как символ a3 входит и в первое, и во второе уравнения, то искажён именно он. Этот символ в принятом кодовом слове заменяется на противоположный. Получается кодовое слово 0110011, совпадающее с переданным.
Рассмотренный пример позволяет построить обобщенную структурную схему декодера линейного кода, показанную на Рисунок 52.
Наиболее сложным устройством декодера, определяющим возможность его реализации, является анализатор синдрома. Синдромы ошибок используемых на практике корректирующих кодов могут содержать десятки и сотни элементов, что затрудняет реализацию устройств логического анализа системы проверочных уравнений (1.33). Число логических операций, необходимое для декодирования кодового слова длиной n(сложность декодера ), обычно экспоненциально увеличивается с ростом n. Поэтому усилия разработчиков, в основном, направлены на поиск таких корректирующих кодов и таких методов декодирования, которые упрощали бы процедуру анализа синдрома ошибки.
Существенное упрощение процедуры декодирования достигается при использовании кодов Хэмминга и циклических кодов.