Общая характеристика помехоустойчивого кодирования

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Общая характеристика помехоустойчивого кодирования

И.В. Краснов



Введение

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

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

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

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

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

Цель данной курсовой работы: изучение основных помехоустойчивых кодов.

Объект: Кодирование информации.

Предмет: Помехоустойчивое кодирование информации.

Задачи:

- изучить литературу по теме исследования;

- определить понятие помехоустойчивости;

- рассмотреть основные принципы помехоустойчивого кодирования;

- дать краткую классификацию помехоустойчивых кодов;

- рассмотреть основные помехоустойчивые коды;

- привести особенности практического кодирования.



1. Общие сведения о помехоустойчивом кодировании

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

Код принимаемого языка определяется алфавитом символов и правилами их комбинирования, т.е. правилами построения знаков различного ранга. Число символов в алфавите называется основанием кода. Знаки второго ранга называются кодовыми словами. Если все кодовые слова имеют одинаковое число символов, то код называется равномерным, в противном случае код называется неравномерным. Пример применения равномерного кода приведен в таблице 1.

Таблица 1

Номер сообщения	0	1	2	3	4	5	6	7
Кодовое слово	000	001	010	011	100	101	110	111

Кодовые слова в этом примере являются записью номера сообщения в равномерном двоичном коде (системе счисления) при числе символов в коде, равном n. Для повышения надежности связи в ряде случаев используют не все кодовые комбинации, где q - основание кода, а лишь часть из них M < N .

Символы кода можно передать различным образом. Например, символы 1 и 0 можно передать положительным (или отрицательным) напряжением и паузами, гармоническими колебаниями одной частоты и паузами, колебаниями различной частоты или фазы. Сигналы символов могут быть простыми и сложными.

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

1.1 Помехоустойчивость

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

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

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

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

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

1.2. Принципы помехоустойчивого кодирования

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

Вначале будет рассмотрен двоичный канал связи с помехами, приводящими к тому, что ошибки появляются независимо в каждом символе и средняя вероятность ошибки равна Р=0,01. Если требуется рассмотреть произвольный блок из 10 символов на выходе канала, то весьма трудно выявить символы, которые являются ошибочными. Вместе с тем, если считать, что такой блок содержит не более трех ошибок, то мы будем неправы лишь два раза на миллион блоков. Кроме того, вероятность, что мы окажемся правы, возрастает с увеличением длины блока. При увеличении длины блока доля ошибочных символов в блоке стремится к средней частоте ошибок в канале, а также, что очень важно, доля блоков, число ошибок в которых существенно отличается от этого среднего значения, становится очень малой. Простые вычисления помогают понять, насколько верным является это утверждение. Рассмотрев, например, тот же канал, можно вычислить вероятность того, что доля ошибочных символов превышает значение p, и построить график этой функции для нескольких значений длины блока.

При обработке символов блоками, а не одного за другим можно уменьшить общую частоту ошибок. При этом потребуется, чтобы существовала схема кодирования, нечувствительная к ошибкам в некоторой доле символов блока и не приводящая при этом к потере сообщением своей индивидуальности, т. е. не приводящая к ошибочному блоку. Из графиков для различных длин блоков видно, какую именно долю ошибок нужно исправлять, чтобы получить заданную вероятность ошибки блока. Он показывает также, что при фиксированной вероятности ошибки блока доля ошибок, которые нужно исправлять, уменьшается при возрастании длины блока. Сказанное свидетельствует о резервах улучшения характеристик при усреднении шума и о том, что эти резервы возрастают при увеличении длины блока. Таким образом, длинные блоковые коды эффективнее коротких. После того как установлена целесообразность исправления ошибок в символах, возникает следующий логичный вопрос: как это сделать? Ключ лежит в избыточности. После некоторых размышлений читатель поймет, что при исправлении ошибок в сообщении, представляемом последовательностью из n двоичных символов, очень важно учесть, чтобы не все 2n возможных последовательностей представляли сообщения. В самом деле, когда каждая из возможных принятых последовательностей n символов представляет некоторое сообщение, нет никаких оснований считать, что одна последовательность является более правильной, чем любая другая. Продолжая рассуждать таким же способом, можно ясно увидеть, что для исправления всех наборов из t или менее ошибок необходимо и достаточно, чтобы каждая последовательность, представляющая сообщение, отличалась от последовательности, представляющей любое другое сообщение, не менее чем в 2t+1 местах. Например, для исправления всех одиночных или всех двойных ошибок в символах нужно, чтобы каждые две последовательности, представляющие разные сообщения, отличались не менее чем в пяти символах. Каждая принятая последовательность, содержащая два ошибочных символа и, следовательно, отличающаяся от посланной последовательности ровно в двух местах, будет всегда отличаться от всех других последовательностей, представляющих сообщения, не менее чем в трех местах. Число позиций, в которых две последовательности отличаются друг от друга, будем называть расстоянием Хемминга d между этими двумя последовательностями. Наименьшее значение d для всех пар кодовых последовательностей называется кодовым расстоянием и обозначается dmin. Поскольку dmin всегда должно быть на единицу больше удвоенного числа исправляемых ошибок, можно написать t=[(dmin-l)/2], где [ ] обозначает целую часть. Параметр t указывает, что все комбинации из t или менее ошибок в любой принятой последовательности могут быть исправлены. Имеются модели каналов, в которых значение t может быть больше указанного.

Пример. Рассмотрим код, состоящий из четырех кодовых слов 00000, 00111, 11100 и 11011. Каждое кодовое слово используется для представления одного из четырех возможных в сообщении. Поскольку код включает лишь небольшую долю всех 32 возможных последовательностей из пяти символов, можно выбрать кодовые слова таким образом, чтобы каждые два из них отличались друг от друга не менее чем в трех позициях. Таким образом, кодовое расстояние равно трем и код может исправлять одиночную ошибку в любой позиции. Чтобы провести процедуру декодирования при этом коде, каждой из 28 недопустимых последовательностей нужно поставить в соответствие ближайшую к ней допустимую последовательность. Этот процесс ведет к созданию таблицы декодирования, которая строится следующим образом. Вначале под каждым кодовым словом выписываются все возможные последовательности, отличающиеся от него в одной позиции. В результате получается часть табл. 2.

помеха цифровой кодирование

Таблица 2. Таблица декодирования для кода с четырьмя словами

00000	11100	01111	11011
10000	01100	10111	01011
01000	10100	01111	10011
00100	11000	00011	11111
00010	11110	00101	11001
00001	11101	00110	11010
10001	01101	10110	01010
10010	01110	10101	01001

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

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

Рte(1 -Рe)5-i (1)

Необходимо отметить что при Рe<1/2 (1 -Рe)5Pe(1 -Рe)4Рe2(1 -Рe)3...

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

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

Ne>=1+n+Cn2+...+Cnt, (2)

где Cni - i-й биномиальный коэффициент.

Неравенство (2) следует непосредственно из того, что имеется ровно n различных последовательностей, отличающихся от данной последовательности в одной позиции, Cn2 последовательностей, отличающихся в двух позициях, и т. д. Как и в приведенном выше простом примере, после размещения всех последовательностей, отличающихся от кодовых в t или менее позициях, почти всегда остаются неразмещенные последовательности [отсюда неравенство в (2)]. Теперь можно связать избыточность кода c числом ошибок, которые им исправляются Заметим сначала, что число всех возможных последовательностей равно 2n. Каждый столбец таблицы декодирования содержит Ne таких последовательностей, поэтому общее число кодовых слов должно удовлетворять неравенству

Ne<=<2n/(1+n+Cn2+...+Cnt), (3)

Это неравенство называется границей Хемминга или границей сферической упаковки. Равенство в (3) достигается только для так называемых совершенных кодов. Эти коды исправляют все наборы из t или менее ошибок и не исправляют никаких других наборов. Число известных совершенных кодов очень невелико, так что равенство в (1.3) достигается в очень редких случаях.

Процесс кодирования состоит в том, что наборы k информационных символов отображаются в кодовые последовательности, состоящие из n символов. Любое такое отображение будем называть (n, k)-кодом, хотя обычно такое название применяется только к линейным кодам (которые обсуждаются позже). Поскольку число последовательностей длиной k равно 2k, неравенство (3) можно переписать следующим образом:

2k<=2n/(1+n+Cn2+...+Cnt), (4)

Мера эффективности кода определяется отношением

R=k/n (5)

и называется скоростью кода. Доля избыточно передаваемых символов равна 1-R.

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

Таблица 3. Таблица поиска при декодировании

Входная последовательность	Кодовая последовательность
00	00100
01	01111
10	11011
11	1000



Часть кодовой последовательности, заключенная между штриховыми линиями, совпадает с входной последовательностью. Поэтому каждой кодовой последовательности, легко однозначно сопоставить входную последовательность. Не все блоковые коды обладают этим свойством. Те, которые им обладают, называются систематическими кодами. Понятие избыточных символов для систематических кодов становится абсолютно ясным, и избыточными символами в табл. 2 являются символы на позициях 1, 4 и 5. Коды, не обладающие указанным свойством, называются несистематическими.

Существует много хороших конструктивных методов кодирования, позволяющих исправлять кратные ошибки и приводящих к заметному уменьшению частоты появления ошибочных символов. Эти коды легко строятся и с помощью современных полупроводниковых устройств относительно просто декодируются. Например, существует блоковый код длиной 40, содержащий 50% избыточных символов и позволяющий исправлять четыре случайные ошибки. При Рe=0,01 этот код имеет вероятность ошибки блока, меньшую 10-4. Если этого недостаточно, разработчик увеличивает избыточность, чтобы исправлять большее число ошибок, или переходит к кодам с большей длиной блока и получает выигрыш за счет большего усреднения. В каждом случае нужно принимать во внимание возникающие дополнительные затраты. Однако обе указанные возможности допустимы и могут представлять практически приемлемые альтернативы. Прежде чем идти дальше, сделаем небольшое отступление, которое не имеет большого практического значения, но привлекает внимание специалистов по теории кодирования в течение многих лет. Форма кривых позволяет предположить, что если имеется схема, исправляющая фиксированную долю t/n ошибочных символов в блоке (в нашем случае t/n незначительно превышает 0,01), то, выбирая длину блока достаточно большой, можно сделать долю ошибок сколь угодно малой. К сожалению, это оказывается очень трудной задачей. Большинство конструктивных процедур может обеспечить постоянное отношение t/n лишь при возрастающей доле избыточных символов (другими словами, R?0 при n??). Таким образом, потеря эффективности возникает из-за того, что доля полезных сообщений становится очень малой при большой длине блока. Частично эта задача была решена Юстесеном в 1972 г. Юстесен показал, что можно построить класс асимптотически «хороших» кодов и указать для них процедуру декодирования. Однако, насколько известно, эти коды не применялись ни в одной из существующих систем связи.

1.3 Основные параметры помехоустойчивых кодов

Проблема повышения верности обусловлена не соответствием между требованиями, предъявляемыми при передаче данных, и качеством реальных каналов связи. В сетях передачи данных требуется обеспечить верность не хуже 10-6- 10-9, а при использовании реальных каналов связи и простого (первичного) кода указанная верность не превышает 10-2-10-5.

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

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

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

Задача кодирования заключается в получении при передаче для каждой k - элементной комбинации из множества qk соответствующего ей кодового слова длиною n из множества qn.

Задача декодирования состоит в получении k - элементной комбинации из принятого n - разрядного кодового слова при одновременном обнаружении или исправлении ошибок.

Основные параметры помехоустойчивых кодов:

Длина кода - n;

Длина информационной последовательности - k;

Длина проверочной последовательности - r=n-k;

Кодовое расстояние кода - d0;

Скорость кода - R=k/n;

Избыточность кода - Rў;

Вероятность обнаружения ошибки (искажения) - РОО;

Вероятность не обнаружения ошибки (искажения) - РНО.

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

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

Основные зависимости между кратностью обнаруживаемых ошибок t0, исправляемых ошибок tu, исправлением стираний tc и кодовым расстоянием d0 кода:

Стиранием называется «потеря» значения передаваемого символа в некоторой позиции кодового слова, которая известна.

Код, в котором каждое кодовое слово начинается с информационных символов и заканчивается проверочными символами, называется систематическим.

Граничные соотношения между параметрами помехоустойчивых кодов.

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

Существуют граничные оценки, связывающие d0, n и k.

Граница Хэмминга, которая близка к оптимальной, для высокоскоростных кодов, определяется соотношениями:

- для q-ного кода

- для двоичного кода

Граница Плоткина, которую целесообразно использовать для низкоскоростных кодов определяется соотношениями:

- для q-ного кода

- для двоичного кода

Границы Хэмминга и Плоткина являются верхними границами для кодового расстояния при заданных n и k, задающими минимальную избыточность, при которой существует помехоустойчивый код, имеющий минимальное кодовое расстояние и гарантийно исправляющий tu - кратные ошибки.

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



2. Коды помехоустойчивого кодирования

2.1 Краткая классификация помехоустойчивых кодов

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

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

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

Коды произведения строят в виде матрицы, в которой строки суть слова одного кода, а столбцы - того же или другого кода.

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

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

Один из наиболее распространенных методов формирования кода произведения заключается в последовательной записи по k1 символов входной информационной последовательности в k2 строк матрицы (например, в ячейки памяти ОЗУ), добавлении избыточных символов по n1-k1 в каждую строку и по n2-k2 в каждый столбец, после чего в последовательность символов кода считывают по строкам или столбцам из матрицы. Физическим аналогом кода произведения является, в частности, частотно-временной код, у которого строки располагаются вдоль оси времени, а столбцы - по оси частот.

Параметры составных кодов: каскадных - n=nвшnвт, k=kвшkвт, d=dвшdвт; произведения - n=n1n2, k=k1k2, d=d1d2.

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

При более широкой трактовке термина «производный код» к этому классу можно отнести все коды, полученные из исходного добавлением или исключением как символов, так и слов.

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

При прочих равных условиях желательно, чтобы информационные и избыточные символы располагались отдельно. В систематических кодах это условие выполняется. В циклических кодах каждое слово содержит все свои циклические перестановки. Все n циклических перестановок (слова длины n) образуют цикл. В квазициклических кодах цикл образуется на числе символов n-1 или, реже, n-2. Циклические коды важны как с точки зрения математического описания, так и для построения и реализации кода.

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

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

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

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

Далее рассматриваются два типа кодов: блоковые и древовидные. Определяющее различие между кодерами для кодов этих двух типов состоит в наличии или отсутствии памяти. Кодер для блокового кода является устройством без памяти, отображающим последовательности из k входных символов в последовательности из n выходных символов. Термин «без памяти» указывает, что каждый блок из n символов зависит только от соответствующего блока из k символов и не зависит от других блоков. Это не означает, что кодер не содержит элементов памяти. Важными параметрами блокового кода являются n, k, R=k/n и dmin. На практике значения k лежат между 3 и несколькими сотнями, a R= =1/4 ...7/8. Значения, лежащие вне этих пределов, являются возможными, но часто приводят к некоторым практическим трудностям. Входные и выходные последовательности обычно состоят из двоичных символов, но иногда могут состоять из элементов некоторого алфавита большего объема. Кодер для древовидного кода является устройством с памятью, в которое поступают наборы из m двоичных входных символов, а на выходе появляются наборы из n двоичных выходных символов. Каждый набор n выходных символов зависит от текущего входного набора и от v предыдущих входных символов. Таким образом, память кодера должна содержать v+m входных символов. Параметр v+m часто называют длиной кодового ограничения данного кода и обозначают k=v+m (не следует путать с параметром k для блокового кода). Отметим, что обозначения часто не согласуются друг с другом. Некоторые авторы называют длиной кодового ограничения параметр k, в то время как другие - параметр v. Здесь длиной кодового ограничения будем называть величину v, поскольку это приводит к меньшей путанице для кодов с m>1. Параметр k=v+m почти не будет использоваться. Древовидные коды характеризуются также скоростью R=m/n и свободным расстоянием dсв. Точное определение dсв более громоздко, чем определение dmin для блоковых кодов, однако параметр dсв, по существу, содержит ту же информацию о коде, что и dmin. Типичные значения параметров древовидных кодов таковы: m, n=1...8, R= 1/4... 7/8, v=2...60.

При другом подходе коды можно разделить на линейные и нелинейные. Линейные коды образуют векторное пространство и обладают следующим важным свойством: два кодовых слова можно сложить, используя подходящее определение суммы, и получить третье кодовое слово. В случае обычных двоичных кодов эта операция является посимвольным сложением двух кодовых слов по модулю 2 (т. е. 1+1=0, 1+0=1, 0+0=0). Это свойство приводит к двум важным следствиям. Первое из них состоит в том, что линейность существенно упрощает процедуры кодирования и декодирования, позволяя выразить каждое кодовое слово в виде «линейной» комбинации небольшого числа выделенных кодовых слов, так называемых базисных векторов. Второе свойство состоит в том, что линейность существенно упрощает задачу вычисления параметров кода, поскольку расстояние между двумя кодовыми словами при этом эквивалентно расстоянию между кодовым словом, состоящим целиком из нулей, и некоторым другим кодовым словом. Таким образом, при вычислении параметров линейного кода достаточно рассмотреть, что происходит при передаче кодового слова, состоящего целиком из нулей. Вычисление параметров упрощается еще и потому, что расстояние Хемминга между данным кодовым словом и нулевым кодовым словом равно числу ненулевых элементов данного кoдового слова. Это число часто называют весом Хемминга данного слова, и список, содержащий число кодовых слов каждого веса, можно использовать для вычисления характеристик кода с помощью аддитивной границы. Такой список называют спектром кода.

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

Как линейные, так и нелинейные коды образуют обширные классы, содержащие много различных конкретных видов помехоустойчивых кодов. Среди линейных блочных наибольшее значение имеют коды с одной проверкой на четность, M-коды (симплексные), ортогональные, биортогональные, Хэмминга, Боуза-Чоудхури-Хоквингема, Голея, квадратично-вычетные (KB), Рида-Соломона. К нелинейным относят коды с контрольной суммой, инверсные, Нордстрома-Робинсона (HP), с постоянным весом, перестановочные с повторением и без повторения символов (полные коды ортогональных таблиц, проективных групп, групп Матье и других групп перестановок).

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

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

2.2 Основные помехоустойчивые коды

Понятие корректирующего кода

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

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

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

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

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

Различают разделимые и неразделимые блоковые коды.

При кодировании разделимыми кодами кодовые операции состоят из двух разделяющихся частей: информационной и проверочной. Информационные и проверочные разряды во всех кодовых комбинациях разделимого кода занимают одни и те же позиции.

При кодировании неразделимыми кодами разделить символы выходной последовательности на информационные и проверочные невозможно.

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

Общие принципы использования избыточности

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

Искажение информации в процессе передачи сводится к тому, что некоторые из передаточных символов заменяются другими - неверными. Так как каждая из разрешенных комбинаций в результате действия помех может трансформироваться в любую другую, то всего имеется 2k*2n возможных случаев передачи. В это число входят:

2k случаев безошибочной передачи;

2k(2k-1) случаев перехода в другие разрешенные комбинации, что соответствует необнаруживаемым ошибкам;

2k(2n-2k) случаев перехода в неразрешенные комбинации, которые могут быть обнаружены.

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

2k(2n-2k)/( 2k*2n)=1-2k/2n (6)

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

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

1-2k/2k+1=1/2 (7)

Основные параметры корректирующих кодов

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

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

r = n - k (8)

Относительной избыточностью корректирующего кода называют величину

Rn=(n-k)/n (9)

или

Rk=(n-k)/k (10)

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

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

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

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

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

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

Число обнаруживаемых ошибок определяется минимальным расстоянием между кодовыми комбинациями. Это расстояние называется хэмминговым.

В безызбыточном коде все комбинации являются разрешенными, =1. Достаточно только исказиться одному символу, и будет ошибка в сообщении.

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

Доказательство. Возьмем значность кода п=3. Возможные комбинации натурального кода образуют следующее множество: 000, 001, 010, 011, 100, 101, 110, 111. Любая одиночная ошибка трансформирует данную комбинацию в другую разрешенную комбинацию. Ошибки здесь не обнаруживаются и не исправляются, так как =1. Если =2, то ни одна из разрешенных кодовых комбинаций при одиночной ошибке не переходит в другую разрешенную комбинацию.

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

- 000, 011, 101, 110 - разрешенные комбинации;

- 001, 010, 100, 111 - запрещенные комбинации.

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

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

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

Ошибки можно не только обнаруживать, но и исправлять.

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

Доказательство. Пусть, как и в предыдущем примере, п=3. Примем разрешенные комбинации 000 и 111 (кодовое расстояние между ними равно 3). Разрешенной комбинации 000 поставим в соответствие подмножество запрещенных комбинаций 001, 010, 100. Эти запрещенные комбинации образуются в результате возникновения единичной ошибки в комбинации 000.

Аналогично разрешенной комбинации 111 необходимо поставить в соответствие подмножество запрещенных комбинаций 110, 011, 101. Если сопоставить эти подмножества запрещенных комбинаций, то очевидно, что они не пересекаются:

В общем случае исправляемые ошибки кратности связаны с кодовым расстоянием соотношением =2 +1.

Для ориентировочного определения необходимой избыточности кода при заданном кодовом расстоянии d можно воспользоваться верхней граничной оценкой для r = n - k, называемой оценкой Хэмминга:

r = n - k (11),

где - сочетание из п элементов по t (число возможных ошибок кратности t на длине п-разрядной комбинации).

Если, например, п=7, =1, то =3, n - k (1+7)=3.

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

Групповой код с проверкой на четность.

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

Строки образуются последовательно по мере поступления символов исходного кода. Затем после формирования т строк матрицы производится проверка на четность ее столбцов и образуются контрольные символы. Контрольные символы образуются путем суммирования по модулю 2 информационных символов, расположенных в столбце:

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

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

Если проверка проводится по строкам и столбцам, то код называется матричным.

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

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

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

Коды с постоянным весом.

Весом называется число единиц, содержащихся в кодовых комбинациях. Если число единиц во всех комбинациях кода будет постоянным, то такой код будет кодом с постоянным весом. Коды с постоянным весом относятся к классу блочных неразделимых кодов, поскольку здесь невозможно выделить информационные и проверочные символы. Наибольшее применение получили коды «3 из 7», «3 из 8», хотя возможны другие варианты. Первая цифра указывает на вес кода, вторая - на общее число символов в комбинации.

Разрешенными комбинациями кода «3 из 7» являются такие, которые содержат три единицы независимо от их места в комбинации, например 1110000 или 1010100 и т.д. Обнаружение ошибок сводится к определению их веса. Если вес отличается от заданного, то считается, что произошла ошибка. Код обнаруживает веса ошибок нечетной кратности и части ошибок четной кратности. Не обнаруживаются ошибки, при которых несколько единиц превращается в нули и столько же нулей - в единицы (ошибки смещения), так как при этом вес кода не изменяется.

В коде «3 из 7» возможных комбинаций сто двадцать восемь ( =128), а разрешенных кода только тридцать пять. Относительная избыточность отн = 0,28.

Циклические коды.

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

- комбинация циклического кода;

- также комбинация циклического кода.

При рассмотрении циклических кодов двоичные числа представляют в виде многочлена, степень которого (п - 1), п - длина кодовой комбинации.

Например, комбинация 1001111 (п=7) будет представлена многочленом

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

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

Построение комбинаций циклического кода возможно путем умножения исходной комбинации А(х) на образующий полином G(x)с приведением подобных членов по модулю 2:

- если старшая степень произведения не превышает (п - 1), то полученный полином будет представлять кодовую комбинацию циклического кода;

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

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

...