Вернер М. Основы кодирования (2004) (1151849), страница 17
Текст из файла (страница 17)
Применяя информационную технику, мы должны учитывать возможность возникновения ошибок (вероятность ошибок) при передаче и храненииинформации. Это в первую очередь относится к• хранению информации на носителях с высокой плотностью записи (магнитные носители, 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 к.Замечание. В литературе часто единичная матрица ставится напервое место.
Заметим, что перестановка столбцов матрицы неоказывает никакого влияния на корректирующую способность кода.Таким образом, в кодовом векторе систематического кода всегдаможно выделить информационные и проверочные символыV = (Щ..Vn-k-1••• Vn-lVn-kn-fc проверочных символов)• (2.6)к информационных символовРоль проверочных символов и их использование будут подробноразъяснены в следующих разделах.2.3. Синдромное декодированиеЗадача декодера заключается в том, чтобы используя структуру кода, по принятому слову г, восстановить переданный информационный вектор.Д л я рассмотренного выше (7, 4)-кода Хэмминга можно предложить следующий алгоритм обнаружения ошибок.
Так как рассматриваемый код является систематическим, выразим каждый из трехпроверочных символов через символы информационного вектора VQ == v-s © «5 ® Щ, Vi = г>з © «4 Ф «5 и «2 = V4 © v$ © v&. ЕСЛИ в канале про-изошла ошибка, то в принятом векторе г хотя бы одно из равенств небудет выполняться. Запишем полученные проверочные соотношенияв виде системы уравнений для компонент вектора г:го©П©7-зФг5ф г6фг3® г4© г5©Г5ФГ6©==s0«1=S2-(2.7)Таким образом, из первых трех столбцов порождающей матрицы G(2.2), мы получили систему трех проверочных уравнений, в которойоперация ф производится по правилам арифметики но модулю 2 (см.табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
