Глава 3. ВИДЫ КОРРЕКТИРУЮЩИХ КОДОВ

3.1. ЗАДАЧИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ

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

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

Пусть передача дискретных сообщений осуществляется по дискретному каналу с входами и выходами. Такой канал получается при квантовании области приема каждого из сигналов на зон. При получается жесткий канал. При квантование отсутствует и получается канал с дискретным входом и непрерывным выходом (полунепрерывный канал). В данной главе, как правило, будет рассматриваться либо двоичный канал либо -ичный симметричный канал с равновероятными ошибками, так как в этом случае синтез СКК прост. Более сложные случаи соответствуют и более сложной задаче синтеза СКК. О них речь пойдет ниже.

В соответствии с рис. 3.1 информационные символы поступают с источника сообщений на кодер блоками -ич-ных символов. Кодер выдает в канал информацию блоками -ичных символов. Эти блоки (кодовые слова) посимвольно передаются по каналу, в котором к ним аддитивно

Рис. 3.1 Схема линии связи с корректирующим кодом

примешиваются шумовые символы На выходе канала получаем вектор причем символы являются -ичными. Каждый символ можно разбить на жесткое решение и информацию о его надежности , (при надежность отсутствует). Жесткое решение вычисляется по формуле где соответствующий шумовой символ канала (ошибка при ), а суммирование должно обладать свойством замкнутости (например, выполняться в конечном поле На выходе декодера появляются -ичные информационные слова которые отправляются получателю сообщений. Данная схема соответствует блочному помехоустойчивому кодированию, в отличие от непрерывного (сверточного), когда нельзя выделить блоки символов, не зависящие друг от друга. В этой книге в основном рассматриваются СКК, основанные на блочных кодах, за исключением некоторых способов и средств практического использования Исходя из изложенного в данной главе подробно будут рассмотрены только блочные коды.

При кодировании множество информационных слов ставится во взаимно однозначное соответствие с множеством кодовых слов при помощи функций Если множества слов над полем -линейная над этим полем функция, то код называется линейным.

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

По своему виду все алгоритмы декодирования можно разделить на два больших класса — вероятностные и невероятностные (хотя возможны и смешанные алгоритмы). Невероятностные алгоритмы, как правило, основаны на решении некоторых уравнений в

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

Теория кодирования, начиная с первых работ Шеннона и Хэммингу, развивалась как самостоятельная научная дисциплина и к настоящему времени накопила существенный теоретический и практический багаж. Ввиду малого объема главы невозможно отразить даже небольшую часть исследований в этой области. Интересующихся отсылаем к монографиям советских и иностранных авторов [24—37].

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

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

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

3. Согласование характеристик кодов, алгоритмов декодирования и канала связи.

Перейдем теперь к краткой характеристике кодов.

Определение 3.1. Блочный код мощности над алфавитом из символов определяется как множество -ичных последовательностей длины называемых кодовыми словами. При код обозначается а величина называется скоростью кода.

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

Определение 3.3. Расстоянием по Хэммингу между двумя -ичными последовательностями длины называется число позиций, в которых они различны.

Определение 3.4. Пусть код. Тогда минимальное расстояние кода А равно наименьшему из всех расстояний по Хэммингу между различными парами кодовых слов, т. е.

Код А с минимальным расстоянием может обозначаться также -кодом.

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

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

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

Пример 31. Двоичный код с проверкой на четность имеет параметры Он имеет один проверочный символ, равный сумме по модулю два всех информационных, и способен исправить одиночное стирание или обнаружить одиночную ошибку Скорость кода очень высока:

Пример 3.2. Двоичный код с повторением имеет параметры Все символы каждого из двух кодовых слов этого кода одинаковы. Он способен исправить ошибок и стираний, если Скорость кода очень низка

Пример 3.3 Двоичный код Хэмминга имеет параметры . Он способен исправить либо одну ошибку, либо два стирания, либо обнаружить две ошибки. Скорость кода