Краткие сведения из теории. Кодер источника, или первичный кодер, осуществляет эффективное кодирование, т

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

Однако двоичные слова первичного кодера не в состоянии противостоять действию помех, т. к. любая ошибка переводит одну разрешенную кодовую комбинацию в другую разрешенную. Для того чтобы ошибки можно было обнаруживать и исправлять, необходимо, чтобы число возможных кодовых комбинаций было больше числа разрешенных. Эту задачу выполняет кодер канала, или вторичный кодер, который к k символам первичного кодера добавляет по определенным правилам r проверочных символов. Общая длина кодового слова на выходе кодера канала становится равной n = k + r, и общее число возможных кодовых комбинаций (N = 2 ⁿ) будет намного больше числа разрешенных (M = 2 ^k), что дает возможность обнаруживать и исправлять ошибки в тех или иных позициях кодового слова канала.

Пример. Код задан производящей (генераторной) матрицей:

.

Параметры кода: n – длина кодовой комбинации (количество столбцов в матрице), n = 6.

Каждая строка матрицы [ G ] состоит из k информационных символов и r проверочных:

.

Разбиваем [ G ] на 2 части так, чтобы слева осталась единичная матрица[1]; k равно количеству столбцов в этой единичной матрице(k = 3).

,

где E_k – единичная подматрица k -го (3-го) порядка;

R – проверочная подматрица.

Определим N – количество возможных кодовых комбинаций длиной n:

, кодовые комбинации.

Определим М – количество разрешенных кодовых комбинаций:

, кодовых комбинаций.

Построим проверочную матрицу. Она состоит из двух подматриц:

,

где R_Т – транспонированная[2] матрица R;

Е_n-k – единичная подматрица порядка n - k.

Запишем уравнения проверок (по [ H ]). В уравнение входят только те разряды, которым соответствуют единицы в соответствующих строках матрицы [ H ]:

Составим таблицу исправлений (синдромов[3]) для информационных разрядов:

Кодовое расстояние d _min равно числу единиц в строке матрицы [ G ] с минимальным весом[4]: d _min = 3.

Количество обнаруживаемых ошибок (кратность ошибки) определяется из неравенства:

,

где Q – кратность ошибки.

, Q £ 2.

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

Количество исправляемых ошибок определяется из неравенства:

.

, Q £ 1.

Таким образом, код может исправить только одиночную ошибку (ошибку в одном разряде).

Схемы кодера и декодера

Суммирование и вычитание по модулю два – операции эквивалентные. Поэтому алгоритм формирования контрольных символов можно получить, переписав уравнения проверок:

.

Кодер состоит из n -разрядного универсального регистра сдвига и n – k = r сумматоров по модулю два (в нашем случае сумматора три). В регистр можно одновременно записать k информационных символов (в нашем случае три). После этого формируются контрольные символы, согласно уравнениям проверок. Схема кодера приведена на рис. 2.1.

Рис. 2.1

Схема декодера, обнаруживающего ошибки, такжесоставляется по уравнениям проверок.

Регистр также n -разрядный. Сумматоров столько же, сколько и в схеме кодера, только у каждого из них на один вход больше. Если ошибок не было, то уравнения проверок выполняются и на входах и выходе схемы «ИЛИ» – нули. Если хотя бы в одной позиции была ошибка, то хотя бы на одном из входов и выходе появится «1», что сигнализирует об ошибке. Схема декодера, обнаруживающего ошибки, приведена на рис. 2.2.

Рис. 2.2

Схема декодера, исправляющего одиночную ошибку, приведена на рис. 2.3.Работает декодер следующим образом. Кодовые комбинации из канала в последовательном режиме записываются в регистр Рег. 1. С помощью трех сумматоров по модулю два осуществляется проверка на наличие ошибки в информационных разрядах, согласно уравнениям проверок. В зависимости от номера разряда, в котором произошла ошибка, на выходах 1-го, 2-го и 3-го сумматоров будут различные кодовые комбинации. Если ошибка произошла в разряде a ₁, то на выходах трех сумматоров появится комбинация 101, т.к. a ₁ подается на первый и третий сумматоры; если ошибка в разряде a ₂ – комбинация 110 (a ₂ подается на первый и второй сумматоры); если ошибка в разряде a ₃ – комбинация 011 (a ₃ подается на второй и третий сумматоры). Если ошибки нет, то кодовая комбинация будет 000. Эти кодовые комбинации называются синдромами ошибок.

Анализ синдромов осуществляет дешифратор синдромов (ДС). Он имеет три выхода. При наличии ошибки «1» появится на том выходе, в какой позиции произошла ошибка. На остальных выходах – нули.

Ошибка исправляется следующим образом. Для исправления ошибки нужно знать номер позиции, в которой она произошла. Как следует из таблицы истинности для двухвходового сумматора по модулю «два», если на одном входе «0», то для второго входа сумматор работает как повторитель. Если же на одном из входов «1», то для второго входа он работает как инвертор. Очевидно, что для того чтобы исправить ошибку в двоичном коде, надо ошибочный разряд инвертировать. Например, произошла ошибка в разряде a ₁. Синдром ошибки будет 101, на выходе дешифратора синдромов – 100. Поэтому второй и третий разряды инвертированы не будут, а первый разряд будет инвертирован. Таким образом, в регистр Рег. 2 запишется исправленная информационная кодовая комбинация, которую примет получатель информации.

Рис. 2.3

Исходные данные для решения задач[5]:

Таблица 2.1

G
G

Таблица 2.2

H
H

Таблица 2.3

Вариант	Схема кодирующего устройства	Вариант	Схема кодирующего устройства

[1] Единичная матрица – это квадратная матрица, у которой по главной диагонали единицы, а все остальные символы – нули.

[2] Транспонированной называют матрицу, строками которой являются столбцы, а столбцами – строки исходной матрицы.

[3] Синдромы (исправляющие векторы кодовой комбинации) – это столбцы проверочной матрицы.

[4] Вес кодовой комбинации равен количеству «1» в ней.

[5] Вариант в таблице 2.1 определяется по предпоследней цифре учебного шифра.

Вариант в таблице 2.2 определяется по последней цифре учебного шифра.

Вариант в таблице 2.3 определяется по разнице последней и предпоследней цифр учебного шифра.

Поиск по сайту: