кодирование и декодирование линейных кодов

1.4.2. Методы кодирования и декодирования линейных кодов

Правила кодирования линейного кода задает проверочная матрица.

Пусть матрица H определена следующим образом:

, (1.33)

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

Структурная схема кодирующего устройства, задаваемого проверочной матрицей , приведена на рис.1.9.

Алгоритм декодирования включает в себя вычисление и анализ синдрома . Если R(x)=0, то принятое кодовое слово считается неискаженным. Если R(x), то приемник отвергает принятое кодовое слово.

Структурная схема декодера, определенного проверочной матрицей (1.33), представлена на рис.1.10.

1.4.3. Методы кодирования и декодирования свёрточных кодов

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

Структура кодера определяется длиной регистра, числом сумматоров и связями каждого сумматора с регистром. Связи выражают двоичным числом (или порождающим полиномом). Единицы в разрядах числа указывают на наличие связей соответствующих отводов регистра с сумматором.

Например, приведенная на рис.1.11 схема кодера соответствует сверточному коду, определенному порождающими полиномами =(111), =(101).

Способ представления связи между входными и выходными последовательностями называется решетчатой диаграммой (рис.1.12). Для решетчатой диаграммы характерны следующие утверждения:

состоит из узлов и ребер (ветвей);

число ребер, исходящих из узла, равно основанию кода;

выходные символы записываются над ветвями;

надписи около узлов характеризуют логическое состояние кодирующего устройства;

каждой информационной последовательности символов соответствует определенный путь на диаграмме;

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

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

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

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

а)

б)

в)

На третьем такте работы декодера (рис.1.13а) общее число путей равно 8. Декодер сравнивает метрики для пар путей, ведущих в каждый узел, и из каждой пары оставляет путь с меньшим весом:

Расчет веса пути для первого узла

Расчет веса пути для второго узла

Таким образом, для первого узла на диаграмме выбирается путь с весом (рис.1.13а), для второго узла – путь с весоми т.д. На четвертом такте работы (рис.1.13б) для первого узла на диаграмме выбирается путь с весом, для второго узла – путь с весоми т.д. Процесс сравнения веса пар путей, ведущих в каждый узел, повторяется на каждом такте.

Глубина (число тактов), на которой происходит слияние путей, является случайной величиной, зависящей от ошибок в принятой последовательности, и заранее не может быть вычислена. Поэтому при практической реализации декодера устанавливают некоторую фиксированную глубину декодирования. В примере на 10-м такте первые восемь ветвей всех «выживших» путей совпадают (рис.1.13в). В этот момент согласно алгоритму Витерби, принимается решение о принятых символах.

Источник

1.3. Кодирование и декодирование линейных блоковых кодов

1.3.1. Кодирование с помощью матриц g и н

Равенство (1.10) определяет по существу правило кодирования для линейного блокового кода, которое может быть использовано непосредственно. Если кодирование должно быть систематическим, то произвольная порождающая матрица G линейного блокового (n, к, d_min) кода С может быть преобразована к систематической форме G_sys (иначе, к канонической форме) с помощью элементарных операций и перестановок столбцов матрицы. Матрица G_sys состоит из двух подматриц: k×k единичной матрицы, обозначаемой I_k, и k× (n-k) проверочной подматрицы Р. Таким образом,

(1.14)

(1.15)

Так как GH T = 0, то отсюда следует, что систематическая форма проверочной матрицы имеет вид

(1-16)

Пример 3. Рассмотрим двоичный линейный (4,2,2) код с порождающей матрицей

Перестановкой второго и четвертого столбцов преобразуем эту матрицу в систематическую форму

Таким образом, проверочная подматрица равна

В дальнейшем будет использовано обозначение u = (u₀, u₁,…,u_k-1) для информационного сообщения и обозначение v = (v₀, v_l. v_n-1) для соответствующего кодового слова кода С.

Если параметры С таковы, что k (n-k) или k/n > 1/2, тогда кодирование с помощью проверочной матрицы Н требует меньшего количества вычислений. Этот вариант кодирования основан на уравнении (1.12) (u, v_p)H T = 0. Проверочные позиции (v_k, v_k+1, …, v_n-1) вычисляются следующим образом:

(1.18)

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

Пример 4. Рассмотрим двоичный линейный (4,2,2) код из примера 3. Пусть сообщение и кодовые слова обозначены u = (u₀,u₁) и v = (v₀, v₁, v₂, v₃), соответственно. Из уравнения (1.18) получаем

Соответствие между 2 2 = 4 двух битными сообщениями и кодовыми словами имеет следующий вид:

(1-19)

1.3.2. Декодирование по стандартной таблице

В этом разделе представлена процедура декодирования, которая находит кодовое слово v, ближайшее к принятому с искажениями слову r = v + е, где вектор ошибок е <0, 1>создан двоичным симметричным каналом (ДСК) в процессе передачи кодового слова. Модель ДСК показана на Рисунке 5. По предположению переходная вероятность р (или параметр ДСК) меньше 1/2.

Рис. 5. Модель двоичного симметричного канала.

Стандартной таблицей (или стандартной расстановкой) для двоичного линейного (n, k, d_min) кода С называется таблица всех возможных принятых из канала векторов r, организованная таким образом, что может быть найдено ближайшее к r кодовое слово v.

Таблица 1. Стандартная таблица двоичного линейного блокового кода.

Стандартная таблица содержит 2 n — k строк и 2 к + 1 столбцов. Правые 2 к столбцов таблицы содержат все вектора из пространства V₂= <0,1>n

Для описания процедуры декодирования необходимо ввести понятие синдрома. Определение синдрома произвольного слова из V₂ следует из уравнения (1.12),

(1-20)

где Н проверочная матрица кода С. Покажем, что синдром является индикатором вектора ошибок. Предположим, что кодовое слово v С, переданное по ДСК, принято как r = v + е. Синдром принятого слова равен

(1.21)

Таким образом, вычисление синдрома можно рассматривать как линейное преобразование вектора ошибок.

Процедура построения стандартной таблицы

Правые столбцы первой строки заполним кодовыми словами кода С, начиная с нулевого кодового слова. В первую ячейку первого столбца запишем нулевой синдром. Положим j = 0.

Для j =j + 1, найдем слово е_j V₂ минимального веса Хемминга, не являющееся кодовым и не включенное в предыдущие строки таблицы. Соответствующий синдром s_j = e_jH T запишем в первый (крайний левый) столбец j-ой строки. В оставшиеся 2 к ячеек этой строки запишем суммы e_j и содержимого первой строки (т.е. кодового слова).

3. Повторяем шаг 2 процедуры, пока все вектора из V₂ не окажутся включенными в таблицу. Эквивалентно, повторяем шаг 2 пока j п-к , иначе Стоп.

Пример 5. Стандартная таблица двоичного линейного (4,2,2) кода:

Декодирование с помощью стандартной таблицы выполняется следующим образом. Пусть r = v +е принятое слово. Найдем это слово в таблице и возьмем в качестве результата декодирования сообщение u, записанное в верхней (первой) ячейке того столбца, в котором лежит принятое слово r. По идее, этот процесс требует хранения в памяти всей таблицы и поиска в ней заданного слова.

Синдром всех элементов i-ой строки равен

(1.22)

и не зависит от конкретного значения кодового слова v С. Упрощенная процедура декодирования состоит в следующем: вычислить синдром принятого слова r = е_j + v

и найти его в левом столбце стандартной таблице; взять лидер смежного класса е_j из второго столбца той же строки и прибавить его к принятому слову, получив ближайшее к принятому r = е’_j + v’ кодовое слово v’.

Пример 6. Снова рассмотрим двоичный линейный (4, 2, 2) код из Примера 3. Положим, что передано было кодовое слово (0110), а принято слово (0010). Тогда синдром равен

Находим в стандартной таблице лидер смежного класса (0100) и получаем декодированное кодовое слово (0010)+(0100)=(0110). Одиночная ошибка в слове исправлена! Это может показаться странным, так как минимальное кодовое расстояние равно 2 и, согласно условию (1.8), исправление однократных ошибок невозможно. Однако объяснение этому может быть найдено в стандартной таблице (Пример 5). Заметим, что третья строка таблицы содержит два различных двоичных вектора веса 1. Это означает, что только три из возможных четырех одиночных ошибок могут быть исправлены. В Примере 6 дана одна из исправляемых ошибок.

В случае систематического кодирования рассмотренная выше процедура находит оценку переданного сообщения на первых k позициях декодированного слова. Это может быть одной из возможных причин применения систематического кодирования.

Источник

ДЕКОДИРОВАНИЕ ЛИНЕЙНЫХ КОДОВ

Существует три основных метода декодирования линейных кодов:

— декодирование по максимуму правдоподобия (по минимуму расстояния);

— мажоритарное декодирование (по большинству проверок);

— декодирование по синдрому.

Декодирование по максимуму правдоподобия

В качестве переданного слова следует выбирать слово, которое ближе всего по Хэммингу к принятому .

Рисунок 5.1 – Структурная схема декодера по минимуму расстояния.

На рисунке: УСр – устройство сравнения; ГКС – генератор кодовых слов; РУ – решающее устройство.

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

Мажоритарное декодирование

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

Существует три способа построения систем проверочных уравнений для декодирования символа:

— системы с разделенными проверками – символ, относительно которого разделяется система, входит во все уравнения. Любой другой символ входит не более, чем в одно уравнение. Для коррекции ошибок необходимо уравнений в системе;

— системы с -связанными проверками – символ, относительно которого разрешается система, входит во все уравнения. Любой другой символ входит не более, чем в уравнений. Для коррекции ошибок необходимо уравнений в системе;

— системы с квазиразделенными проверками – система разделима относительно некоторой суммы символов. На первом этапе она разрешается относительно суммы символов, а на втором – относительно конкретного символа.

Рисунок 5.2 – Структурная схема мажоритарного декодера.

На рисунке: 1…k – устройства, реализующие проверки для соответствующей системы; МЭ – мажоритарный элемент, принимающий решение о значении символа по большинству результатов проверок.

Код (8,4) задан матрицей:

.

Система уравнений по матрице Н:

Система проверочных уравнений для :

Система проверочных уравнений для :

Система проверочных уравнений для :

Система проверочных уравнений для :

Пусть .

Результат декодирования: .

Декодирование по синдрому

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

Таблица – Стандартная таблица.

b_i – кодовые слова;

e_j – векторы ошибок – образцы ошибок минимального веса;

b_i+e_j – слова, не являющиеся кодовыми;

s_i=e_i∙H T – синдромы – векторы размерностью r, указывающие на наличие и расположение ошибок в принятом слове.

1. Вычисляется синдром по принятому слову :

.

Если , то является кодовым словом. В противном случае ( ) содержит ошибки.

2. По находится наиболее правдоподобный вектор ошибки .

3. Ближайшее к принятому кодовое слово получается в результате суммирования и :

.

Рисунок 5.3 – Структурная схема декодера по синдрому.

На рисунке: Б – буфер хранения принятого слова; БВС – блок вычисления синдрома; С – селектор (дешифратор) синдрома; К – корректор.

Данный метод используется, когда число проверочных символов мало ( T =(001)e₃=(00010)b₂+e₃=(01001)b₃+e₃=(10111)b₄+e₂=(11100)s₃=e₃∙H T =(010)e₄=(00100)b₂+e₄=(01111)b₃+e₄=(10001)b₄+e₂=(11010)s₄=e₄∙H T =(100)e₅=(01000)b₂+e₅=(00011)b₃+e₅=(11101)b₄+e₂=(10110)s₅=e₅∙H T =(011)e₆=(10000)b₂+e₆=(11011)b₃+e₆=(00101)b₄+e₂=(01110)s₆=e₆∙H T =(101)e₇=(01100)b₂+e₇=(00111)b₃+e₇=(11001)b₄+e₂=(10010)s₇=e₇∙H T =(111)e₈=(11000)b₂+e₈=(10011)b₃+e₈=(01101)b₄+e₂=(00110)s₈=e₈∙H T =(110)

Пусть (10111). Проведем декодирование.

1. ;

2. ;

3. .

1. [3.1.2] с. 309…312, 317…318;

[3.1.5] с. 147.. 149, 150…151;

[3.1.14] с. 258…261, 271…273.

2. Код (7,4) задан порождающей матрицей:

.

Провести декодирование по синдрому принятого слова .

6 НЕПРЕРЫВНЫЕ (РЕКУРРЕНТНЫЕ) КОДЫ

Общие сведения

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

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

Пакеты ошибок длиной 4 могут быть такими:

К непрерывным кодам относят цепной и сверточные. Цепной код является простейшим случаем сверточных.

Цепной код

В таком коде после каждого информационного символа следует проверочный. Закодированная последовательность имеет вид:

где — шаг сложения. Определяет корректирующие возможности кода;

— информационные символы;

— проверочные символы. Формируются по правилу:

Код позволяет исправить пачки ошибок длиной , если они разделены защитным интервалом .

Сверточные коды (ск)

Это линейные, рекуррентные коды. Название обусловлено тем, что кодирование информации СК представляет собой операцию свертки двух функций:

где — входная последовательность информационных символов;

— номер входа;

— выходная последовательность кодовых символов;

— номер выхода;

— порождающий полином.

Набор порождающих полиномов определяет внутреннюю конструкцию кодера.

Рисунок 6.1 – Обобщенная структурная схема кодера СК.

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

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

Рисунок 6.2 – Структурная схема кодера несистематического СК с и .

Источник