Пример. Кодирование и декодирование линейного кода (6, 3). – ЧАСТЬ 1

Ключевые идеи корректирующего кодирования удобнее всего пояснять имен­но применительно к блоковым кодам. Например, все проверочные биты могут быть линейной комбинацией информационных битов. Классический способ за­дания линейного блокового кода связан с порождающей матрицей G, строки которой – к линейно независимых кодовых слов (базис кода); и проверочной матрицей Н, выбираемой из условия

где U – вектор, описывающий разрешенное слово кода, 0 – нулевая вектор- строка, Т— знак транспонирования. При таком способе задания кода все его разрешенные слова можно получить перемножением вектор-строки из к инфор­мационных символов на порождающую матрицу.

Декодирование сводится к определению вектора ошибок е в принятом с r=U+e. Оно осуществляется путем вычисления синдрома 8=гНг=(и+е)Нг=Л<нт Если S=0, то г принадлежит множеству слов кода. При S^O можно сделать6 вод о наличии в принятом слове ошибок. Если их число (кратность) не ВЫ восходит корректирующую способность кода, то ненулевые элементы синдро^ позволяют однозначным образом локализовать позиции ошибок.

С целью наглядного пояснения сказанного, приведем пример построения декодирования простейшего линейного кода. Пусть вектор сообщения

m = т{, т2,.., тк,

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

12                                                                                                                           п

r=U+e,                                                                                                                       (2.14)

где е = е}, е2,. . , еп~ модель вектора ошибок.

В общем виде процесс построения кодового слова, все элементы которого определяются линейной комбинацией символов вектора сообщения, записыва­ется в виде векторно-матричного уравнения

U = mG.                                                                                                                      (2.15)

Произведение вектора сообщения m на /’-й вектор-столбец G образует /’-й элемент кодового слова.

Порождающая матрица G состоит из коэффициентов (элементов числового поля), определяющих связь проверочных символов с символами сообщения, а перемножение га на G выполняется согласно обычным правилам умножения матриц. В случае двоичного кода, символы вектора сообщения и коэффициенты матрицы G – двоичные числа 0 и 1. Для недвоичных кодов те и другие являются элементами числовых конечных полей, вычисления в которых осуществляются в соответствии с определенными в них арифметическими операциями [21].

Конструктивной формой представления кодового слова U является вариант, при котором вектор сообщения без изменений встраивается в структуру слова с добавлением к нему проверочного блока. Такой код называют систематиче­ским. Согласно (2.15), построение систематического кода описывается выраже­нием

U = mG = ш[Р | IJ.                                                                                                    (2Л }

При этом в порождающей матрице можно выделить две части: провероч

иый блок Р и единичную матрицу 1А размерности /схАг.                                   х

Ограничимся далее обсуждением двоичных кодов, где к информадион^__ бит образуют 2к различных сообщений, а число возможных кодовых ком и^ длиной п равно 2". Кодирование сводится к отображению любого из 2 ве

сообщений в одно из 2* разрешенных слов. При систематическом кодировании эта процедура заключается в добавлении п~к проверочных битов к /с-битовому блоку сообщения. Для линейных кодов, как систематических, так и несистема­тических, преобразование информационных символов в кодовое слово является линейным.

В табл. 2.3 приведен пример отображения вектора сообщения в кодовые сло­ва кода (6,3). При систематическом кодировании в каждом кодовом слове к=Ъ рас­положенных справа бита совпадают с вектором сообщения. Всего существует 2*=23=8 векторов сообщения, которым соответствуют 8 различных разрешенных кодовых слов (общее число кодовых комбинаций длины п=6 равняется 2"=26=64).

Таблица 2.3

Отображение векторов сообщений в кодовые слова кода (6, 3)

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

Поскольку вся совокупность разрешенных кодовых слов является ^-мерным подпространством «-мерного векторного пространства, всегда можно найти набор векторов из менее чем 2к кодовых слов, позволяющий сгенерировать каждое из 2к слов кода. Наименьший набор линейно независимых векторов подпространства называется его базисом, а число векторов в нем – размерностью подпространства. Набор из к линейно независимых «-мерных векторов однозначным образом зада­ет порождающую матрицу кода G [20]. Такая матрица позволяет построить любое кодовое слово как линейную комбинацию базисных векторов V,,V2,.. .,Ук. Каждое из 2к разрешенных слов кода может быть записано в виде

что соответствует переданному сообщению m.

Вышеизложенные идеи и приведенный пример концептуально описывают принцип декодирования линейных кодов, получивших широкое распростране­ние. Их важным с практической точки зрения подклассом являются цикличе­ские коды, в которых циклический сдвиг разрешенного кодового слова также представляет собой разрешенное слово данного кода. Порождающая матрица G циклического кода имеет специфическую структуру: все ее строки являются циклическими сдвигами одной строки. Таким образом, характерное свойство циклического кода – возможность задания его порождающей матрицы цикли­ческими сдвигами одной единственной строки, представляемой с помощью по­рождающего многочлена g(x) степени n~k. Все множество слов циклического кода может быть получено путем умножения всевозможных полиномов степени к-1, характеризующих векторы сообщения, на порождающий полином. Каждо­му кодовому слову сопоставляется многочлен, делящийся без остатка на g(x), с коэффициентами, равными символам слова. Заметим, что, помимо компакт­ности способа задания, такие коды отличает наличие эффективных процедур декодирования. Порождающие полиномы многих хороших циклических кодов: Боуза-Чоудхури-Хоквингема (БЧХ), Рида-Соломона (PC) и др., табулированы.

Среди непрерывных кодов, благодаря простоте технической реализации и значи­тельному выигрышу от кодирования, наиболее популярны сверточные коды. Речь о них и о получаемых на их основе турбокодах пойдет далее, в подразделах 2.3.3,2.3.4.

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

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100