Материал: Статистическая теория систем. практикум. Володько А.В., Останков А.В

1.1.2. Блочные коды, основные характеристики

Большинство блочных кодов относится к линейным систематическим кодам. Название «систематический» означает, что кодовая комбинация из n символов четко разделяется на информационную часть и проверочные символы. Обычно и информационные символы занимают первые k позиций в кодовой комбинации. Последние r позиций,

r = n-k (1)

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

Название «линейный» означает, что проверочные символы формируются на основе каких-то информационных при использовании определенной линейной операции, чаще всего суммирования по модулю два.

Основными характеристиками блочных кодов являются:

-число разрешенных Np и запрещенных N3 кодовых комбинаций,

-хеммингово и кодовое расстояние d,

-веса кодовых комбинаций w.

Поясним коротко каждую характеристику.

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

определяется числом комбинаций по к информационных символов. Остальные комбинации

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

стояние. Это расстояние называется хемминговым, оно определяется как число позиций, в которых одна комбинация отличается от другой. Например, кодовые комбинации 0101110 и 1110010 имеют хеммингово расстояние d = 4. Чтобы проще его определить, целесообразно записать комбинации одну под другой. Сравнение символов в каждой позиции можно заменить суммированием по модулю два. Число «1», полученных в результате суммирования, и даст значение хеммингова расстояния.

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

Вес w кодовой комбинации - это число единичных символов в ней. Веса разрешенных кодовых комбинаций могут быть как одинаковыми, так и различ-

5

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

Линейные систематические коды обозначаются (n,К), где n - длина кодовой комбинации, К - число информационных символов в ней.

1.1.3. Виды декодирования

Коррекция ошибок осуществляется при декодировании принятой кодовой комбинации, при преобразовании ее в последовательность информационных символов. При этом возможны прием «в целом» и последетекторное декодирование. При приеме «в целом» принятая комбинация рассматривается как единый сигнал, который принадлежит к m - ичным сигналам, m = 2K.

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

Рассмотрим поподробнее различные виды декодирования и укажем, какие кратности ошибок будут корректироваться гарантированно при использовании заданного кода, с кодовым расстоянием d.

Декодирование с обнаружением ошибок

Основной принцип такого декодирования - определить, является ли принятая кодовая комбинация разрешенной или запрещенной. Если принята разрешенная комбинация, то информационные символы выдаются получателю, так как считается, что в комбинации нет ошибки (хотя на самом деле она может и быть). Если при декодировании установлен факт, что принята неразрешенная комбинация, то она стирается, то есть информация получателю не выдается. Теперь можно решить вопрос, какие кратности ошибок будут обнаруживаться. Ответ прост: обнаруживаться будут те ошибки, которые не переведут переданную разрешенную кодовую комбинацию в другую разрешенную. Для решения вопроса о кратности обнаруживаемой ошибки вернемся к рассмотрению хеммингова расстояния. Его можно рассматривать как число позиций, занятых искаженными символами в одной комбинации, которое переведет ее в другую. Короче, если для рассматриваемых выше комбинаций хеммингово расстояние d = 4, то четырехкратная ошибка может перевести одну комбинацию в другую.

6

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

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

Декодирование с исправлением ошибки

Отличие от предыдущего вида декодирования состоит в том, что здесь надо определить место ошибки, позицию ошибочного символа, и сформировать сигнал исправления. При декодировании определяется сигнал, который указывает на место ошибки. Этот сигнал называется локатором ошибки. Для определения кратности исправляемой ошибки опять вернемся к понятию хеммингова расстояния и его толкованию, которое мы привели при рассмотрении декодирования с обнаружением ошибки. Назовем искажение одного символа комбинации одним шагом. Тогда комбинация 0101110 перейдет в комбинацию 1110010 за четыре шага.

Распишем эти шаги.

0101110 → 1101110 → 1111110 → 1110110 → 1110010

При каждом шаге переименовывается только один символ, который отмечается точкой внизу. Предположим, что в приведенной выше цепочке две комбинации будут разрешенными: первая 0101110 и вторая 1110010. Остальные комбинации будут запрещенными. Комбинация 1101110 является запрещенной и отстоит от первой разрешенной комбинации на один шаг, а от второй разрешенной - на три шага. Можно сказать, что комбинация 1101110 ближе к первой разрешенной комбинации, чем ко второй. Запрещенная комбинация 1110110 стоит ближе ко второй разрешенной кодовой комбинации, чем к первой. А комбинация 1111110 имеет одинаковые расстояния от первой и второй разрешенной комбинации.

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

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

7

ции своей разрешенной. Зная кодовое расстояние кода, можно ответить на вопрос о кратности исправляемой ошибки:

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

нацией не может быть заменена. Ошибки кратности И d не исправляются.

2

Декодирование с обнаружением и исправлением ошибок

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

Рассмотрим примеры:

Пример 1. Оценить, какие виды декодирования возможны для кода (7,3) с кодовым расстоянием d = 4. Указать допустимые кратности ошибок при каждом виде декодирования.

1) Декодирование с обнаружением ошибок. Кратность обнаруживаемой ошибки согласно формуле (4)

ρо ≤ 4-1 =3

2) Декодирование с исправлением ошибки.

В соответствии с формулой (5) кратность исправляемой ошибки

ρи < 4/2 = 2

3) Декодирование с обнаружением и исправлением ошибок.

Здесь надо помнить, что условие (6) должно выполняться при ρи < ρо, то есть ρи =1, ρо =2.

Таким образом, код (7,3) с кодовым расстоянием d = 4 допускает все три вида декодирования.

8

1.1.4. Описание лабораторной установки

Лабораторный стенд (рис. 1.1) содержит панель, на которой представлены следующие устройства: программное, кодирующее, декодирующее и устройство коррекции ошибок.

Программное устройство, представленное отдельным блоком, содержит генератор тактовых импульсов (КТ7), формирователи сигналов: установки нуля «Уст. 0» (КТ8); импульса опроса «ИО» (КТ9); синхронизации осциллографа (КТ13) (в скобках указаны номера контрольных точек, в которых можно наблюдать соответствующие сигналы). В программное устройство входят также формирователи: сигналов переключения кодирующего устройства (КТ2); сигналов информации («ИНФ» – КТ1); сигналов ошибки («ОШ» – КТ3).

На передней панели лабораторного стенда представлена функциональная схема лабораторной работы. Основными блоками являются кодирующее и декодирующее устройства.

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

Кодирующее устройство может быть собрано с использованием следующих блоков: регистр сдвига Д1, схема И-НЕ Д5, сумматор по модулю два Д3, схема 2И Д4 и схема 2И-ИЛИ Д6, формирователь СП Д2, а также гнезда Г1Г13. Гнезда Г1 - Г4 являются выходами первого, второго, третьего, четвертого разрядов кодирующего регистра. Гнезда Г5 - Г7 являются входами сумматора по модулю два, выход которого через Д4 подключен ко входу регистра.

Гнезда Г1 – Г7 позволяют в соответствии с заданным порождающим полиномом подключить на входы сумматора по модулю два выходы соответствующих разрядов регистра сдвига. Для нормальной работы кодирующего устройства следует правильно выбрать СП, который должен иметь «1» в течение k информационных разрядов.

Выбор СП осуществляется переключением запускающего триггер импульса в 3, 4 или 6 такт. Сигнал в восьмом такте перебрасывает триггер в исходное состояние. Контроль СП проводится в точке КТ2. Гнезда Г9 – Г13 и схема Д5 позволяют подключить к ключам Д4 и Д6 СП прямой или инвертированный в соответствии с требуемой работой ключей. Кодовую комбинацию можно наблюдать в точке КТ5.

В сумматоре Д9 кодовая комбинация складывается по модулю 2 с сигналом ошибки (КТ3) и в контрольной точке КТ6 можно наблюдать сигнал с помехами (кодовая комбинация + ошибка).

На кодирующее устройство подается информация, которая набирается поразрядно с помощью тумблеров и может наблюдаться в КТ1. Верхнее положение тумблера соответствует «1», нижнее – «0». При наборе информации следует помнить, что информационная последовательность – это группа из k двоичных символов, то есть используются первые k тумблеров.

9