Вернер М. Основы кодирования (2004) (1151882), страница 17
Текст из файла (страница 17)
Зависимость между затратами и качеством в системах передачи информации.Здесь на помощь приходит цифровая техника и помехоустойчивое кодирование. Путем применения оптимального кодирования,можно обеспечить как угодно малую BER (при условии R < С).При выборе методов кодирования и декодирования, руководствуются многими факторами, взаимосвязь которых показана на рис. 1.3.В общую сложность входят.аппаратурные и программные затратына реализацию кодера и декодера, цены специализированных микросхем и микропроцессоров, стоимость памяти для хранения информации и т.д.
Интенсивность потока данных включает в себя передачуполезной информации, проверочных разрядов, а также передачу запросов и повторений по этим запросам отдельных блоков сообщений.Способность кода обнаруживатьи исправлять ошибкиИнтенсивностьпотокаданныхР и с . 1.3. Взаимосвязь между параметрами кодовых конструкций.Методы помехоустойчивого кодирования довольно многообразны.
В этой книге мы ограничимся лишь описанием наиболее важныхклассов блоковых и сверточных кодов. При этом, основное вниманиеуделяется циклическим кодам из-за простоты их реализации. Циклические коды образуют подмножество линейных блоковых кодов,поэтому, наш вводный курс мы начнем с описания структуры и общих свойств линейных блоковых кодов (подробнее см., например, [5]).ГЛАВА 2ЛИНЕЙНЫЕБЛОКОВЫЕ КОДЫ2.1.
Помехоустойчивое кодированиеРеальные системы передачи данных не совершенны. Применяя информационную технику, мы должны учитывать возможность возникновения ошибок (вероятность ошибок) при передаче и храненииинформации. Это в первую очередь относится к• хранению информации на носителях с высокой плотностью записи (магнитные носители, CD — ROM, DVD).• передаче данных при ограниченной мощности сигнала (спутниковая и мобильная связь)• передаче информации по сильно зашумлсниым каналам (мобильная связь, высокоскоростные проводные линии связи)• каналам связи с повышенными требованиями к надежности информации (вычислительные сети, линии передачи со сжатиемданных)Во всех вышеперечисленных случаях используются коды, контролирующие ошибки. Теория помехоустойчивого кодирования для каждого конкретного канала позволяет выбрать наиболее эффективныйметод обнаружения и исправления ошибок.
Существуют два взаимодополняющих метода борьбы с помехами.• Кодирование для исправления ошибок - приемник обнаруживает и исправляет ошибки;• Кодирование для обнаружения ошибок приемник распознаетошибки и,чв случае необходимости, производит запрос на повторную передачу ошибочного блока.Последний метод предполагает наличие канала обратной связии находит свое применение в каналах с достаточно малой вероятностью ошибки в случае, если эту вероятность ошибки необходимо2.1. Помехоустойчивое кодированиееще понизить. Такая ситуация часто возникает, в вычислительныхсетях и в интернете. Типичное значение вероятности ошибки на битбез кодирования в вычислительных сетях составляет 10~6.
Использование простейших кодов с небольшой избыточностью позволяетдостигнуть вероятности 10~9 и ниже.Замечание. Требование к вероятности ошибки 10~9 не являетсячрезмерно завышенным. В вычислительных сетях, например, может возникнуть обрыв связи в результате повреждения оптоволокна при производстве земляных работ, небрежного подключениякабеля к модему и т.д. Такой обрыв должен быть быстро обнаружен декодером, который в случае резкого возрастания частотыпереспросов выдает сигнал обрыва связи.В последующих разделах идеи помехоустойчивого кодированиябудут подробно объяснены на примерах линейных блоковых кодов.Здесь же мы рассмотрим простейшую модель передачи данных сиспользованием помехоустойчивого кодирования (рис. 2.1).СообщениеКодерИсточникUКодовое словоКодерКодированиеканалаПолучатель 4-ДекодерДекодерДекодированноесообщениеПринятое словоР и с .
2 . 1 . Модель к а н а л а связи с кодированием.Будем исходить из того, что при передаче информации исполь1зуется блоковый код Хэмминга , структура которого будет подробнораскрыта в дальнейшем. Сейчас мы ограничимся его табличным описанием. Пусть кодер источника последовательно выдает информационные слова фиксированной длины. Кодер канала заменяет каждоеинформационное слово и кодовым словом v в соответствии с табл. 2.1.Передатчик генерирует сигналы, соответствующие кодовому слову v и посылает их в канал. Приемник производит обратное пре1Ричард В. Хэмминг: 1915/1998, американский математик.132Глава 2. Линейные блоковые кодыТаблица 2.1.
Кодовая таблица (7,4)-кода Хэмминга.ИнформационноеКодовоеИнформационноеКодовоесловословословослово0000000 00000001101 00011000П О 10001001011 10010100011 01000101П О 01011100101 11001101000 11010010111 0010ООП010 ООП1010001 10101011100 10110110100 О Н О0111001 01111110010 11101111111 1111образование, в результате которого на декодер поступает двоичноепринятое слово г.Декодер сравнивает принятое слово г со всеми кодовыми словамитабл. 2.1. Если слово г совпадает с одним из кодовых слов, то соответствующее информационное слово G выдается потребителю.
Еслиг отличается от всех кодовых слов, то в канале произошла обнаруживаемая ошибка.2Из всего вышесказанного уже можно сделать два важных вывода:• Если в процессе передачи по зашумленному каналу кодовоеслово отобразится в другое кодовое слово, не совпадающее спереданным, то происходит необнаружимая ошибка. Назовемее остаточной ошибкой декодирования.• «Хорошие коды» обладают некоторой математической структурой, которая позволяет эффективно распознать, а в некоторых случаях и исправлять ошибки, возникающие при передачеинформации по каналу связи.2Из структуры кода Хэмминга следует одно интересное свойство, которое можетбыть проверенно простым перебором:Для любого произвольного вектора г существует ближайшее кодовое слово,которое или полностью совпадает с г или отличается от него только в одномдвоичном разряде.
Таким образом, если в векторе v при передаче по каналупроизошла только одна ошибка, она всегда может быть исправлена в процесседекодирования.- Прим. перев.2.2. Порождающая матрица2.2. Порождающая матрицаВажное семейство кодов образуют линейные двоичные блоковые коды. Эти коды замечательны тем, что представляя информационныеи кодовые слова в форме двоичных векторов, мы можем описатьпроцессы кодирования и декодирования с помощью аппарата линейной алгебры, при этом, компонентами вводимых векторов и матрицявляются символы 0 и 1. Операции над двоичными компонентамипроизводятся по привычным правилам двоичной арифметики, такназываемой, арифметики по модулю 2 (Табл. 2.2).Таблица 2.2. Арифметика по модулю 2.СложениеУмножениее01©01001000110101Замечание.
С математической точки зрения, определив операциис двоичными символами согласно таблице 2.2, мы построили полеГалуа характеристики 2 первого порядка GF(2). Общая теория полей Галуа позволяет строить поля характеристики р порядка т- GF(pm), где р - простое, т - любое конечное целое. Переход кmрасширенным полям GF(p ) дает возможность конструироватькоды, обладающие рядом новых свойств, полезных по сравнению сдвоичными кодами.В частности, коды Рида-Соломона с символами из GF(2m), m >2 с успехом применяются для защиты информации в аудио, CDпроигрывателях (Полям Галуа и кодам Рида-Соломона посвященаглава 5 данной книги).Кодер двоичого блокового (п, /г)-кода отображает множество 2кквозможных двоичных информационных слов в множество 2 га-мерныхкодовых слов (в теории кодирования между этими множествами всегда существует взаимно однозначное соответствие) (см.
рис. 2.2).Вместо к бит информационного вектора в канал передаетсягабиткодового вектора. В этом случае говорят об избыточном кодировании со скоростью(2.1)тЧем ниже скорость, тем больше избыточность кода и тем большимиR=-.Глава 2. Линейные блоковые кодывозможностями для защиты от ошибок он обладает (здесь, однако,надо учитывать, что с увеличением избыточности, затраты на передачу информацию также возрастают).КодовоесловоИнформационноеслово|НЫ)КодерV = (V0,V|,...,V,,.|)Рис. 2.2.
Кодер блокового (п, £)-кода.. Кодирование линейного блокового (п, &)-кода задается порождающей матрицей G/t Xn . В рассмотренном выше (7,4)-коде Хэммингапорождающая матрица имеет вид1 1 0 10 0 00 1 1 0 10 01 1 1 0 0 1010 10 0 0 1(2.2)Таким образом, кодовое слово v и информационное слово и связаны соотношениемv = u©G.(2.3)Например, информационный вектор и = (1010) отображается в кодовый вектор/ 10v = (1010)01V11 011 1 01 1 00 1 00 0 01 0 00 100 0 1= (0011010).(2-4)Первое, что сразу же бросается в глаза из табл.
2.1, это совпадение последних четырех разрядов кодовых слов с информационнымивекторами. Такой код относится к семейству систематических кодов.Коды, в которых информационное слово может быть непосредственно выделено из соответствующего ему кодового вектора, называются систематическими.Порождающую матрицу любого систематического кода всегдаможно путем перестановки столбцов привести к видуGfcxn = (Pfcx(n-fc)(2.5)2.3. Сипдромное декодирование 135)где нижние индексы обозначают размерность матрицы, а 1ц - единичная матрица размерности k x к.Замечание.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
