1.2. Блоковые коды. Систематические коды

Рассмотрим -ичный канал по которому могут передаваться сигналы (импульсы) типов определенной длительности. Для обозначения этих сигналов будем использовать

различных символов, которые назовем символами канала; множество символов канала обозначим через Пусть множество всех последовательностей длины из символов Расстояние Хэмминга между последовательностями длины определим как число пар компонент таких, что а Заметим, что это расстояние зависит лишь от того, совпадают или нет соответствующие символы последовательностей Расстояние Хэмминга может быть использовано в системах модуляции с ортогональными сигналами [4]. Это связано с тем, что, когда символов канала представляют взаимно ортогональных сигналов с равной энергией, а шум в канале является аддитивным белым и гауссовским, вероятность ошибки (т. е. вероятность перехода одного символа канала в другой) для всех сигналов одна и та же. Расстояние Хэмминга применяется также для описания процесса возникновения ошибок в запоминающих устройствах вычислительных машин, в которых разные двоичные символы слова хранятся в различных матрицах [5].

Для описания возникновения ошибок в системах с фазовой модуляцией может быть использовано расстояние Ли [6]. Чтобы ввести это расстояние, необходимо установить взаимно однозначное соответствие между элементами множества и целыми числами от 0 до Здесь для простоты будем считать, что Для каждого элемента определим число следующим образом: если а в противном случае. Расстояние Ли между последовательностями определяется равенством При равном 2 или 3, расстояние Хэмминга сосовпадает с расстоянием Ли. Поскольку в теории кодирования результаты, полученные для расстояния Ли, не являются столь значительными, как результаты, полученные для расстояния Хэмминга, то в данной книге вопросы, связанные с расстоянием Ли, почти не рассматриваются (детальное изложение этих вопросов можно найти в книге Берлекэмпа [4]).

Для описания и исследования методов кодирования в системах с амплитудной модуляцией наиболее подходящим является евклидово расстояние (см. гл. 7), однако в теории кодирования получено лишь несколько частных результатов, посвященных этому вопросу, и они в основном связаны с некоторыми идеями устранения недостатков кодов, построенных для расстояния Хэмминга [7,8].

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

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

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

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

В теории кодирования обычно предполагается, что кодер и демодулятор, точно так же, как и декодер и демодулятор, представляют собой отдельные устройства; при этом каждый символ канала преобразуется и передается независимо от других. Такое построение системы приводит не только к упрощению устройств, но, как мы увидим в гл. 7, и к некоторому снижению пропускной способности канала. Согласно теореме Шеннона для дискретного канала [9] (этот канал будет рассмотрен ниже в разд. 1.5), в случае использования подходящих (блоковых) кодов, исправляющих ошибки, при всех скоростях, меньших пропускной способности канала, информацию можно передавать со

сколь угодно малой вероятностью ошибки. Однако теорема Шеннона является так называемой теоремой существования и не дает конкретных методов построения таких кодов. Разработка практически приемлемых методов кодирования является задачей теории кодирования. Для того чтобы эффективность использования кодов была высокой, необходимо усреднить воздействие шумов. Это приводит к необходимости выбирать длину кода достаточно большой, что в свою очередь обычно связано с чрезмерным усложнением кодеров и декодеров. Например, в случае число кодовых слов достигает приблизительно 1030, а общее число последовательностей длины приблизительно 1060, так что практически построить описанную таблицу декодирования просто невозможно. Этот пример показывает, что построение кодов, которые имели бы достаточно большую длину (а следовательно, и высокую эффективность), но в то же время были бы практически реализуемыми с точки зрения сложности кодера и декодера, является непростой задачей. Коды, удовлетворяющие этим условиям, должны иметь хорошую (алгебраическую) структуру, которая гарантировала бы нужные корректирующие способности и позволяла бы найти практически реализуемые процедуры кодирования и декодирования. Эта точка зрения на цели теории кодирования и пути их достижения была положена в основу исследований, которые велись и ведутся в настоящее время в области алгебраической теории кодирования.

Утверждение 1.5. Если то

Утверждение 1.6. Пусть Тогда необходимым и достаточным условием того, что не содержат общих элементов, является выполнение соотношения

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

2) Пусть Предположим, что существует последовательность принадлежащая одновременно и Тогда Но в таком случае, как следует из утверждения что противоречит предположению.