Вернер М. Основы кодирования (2004) (1151882), страница 18
Текст из файла (страница 18)
В литературе часто единичная матрица ставится напервое место. Заметим, что перестановка столбцов матрицы неоказывает никакого влияния на корректирующую способность кода.Таким образом, в кодовом векторе систематического кода всегдаможно выделить информационные и проверочные символы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 (см.табл. 2.2).
Если в полученной системе уравнений хотя бы одна изкомпонент {.so, si, S2} не равна нулю, то в канале произошла ошибка.Запишем систему проверочных уравнений в общем виде. Для любого систематического кода с порождающей матрицей (2.5), проверочная матрица определяется какH ( n _ f c ) x n = (i n _ f c pL(n-fc))' •28• (-)Глава 2. Линейные блоковые кодыгде Hj.x(n_j.) - транспонированная матрица, т. е. матрица размерности к х (п — к), получаемая из Ркх(п-к) путем замены строк матрицы на ее столбцы. Тогда систему проверочных уравнений можнозаписать в в'идеs = г 0 Н7(2.9)Вектор s принято называть синдромом. Таким образом, ошибка будет обнаружена, если хотя бы одна из компонент s не равна нулю.Равенство (2.9) можно переписать в видеS = Г©(г 1 »-').(2.10)Замечание.
В медицине термин синдром используется для обозначения сочетания признаков, характеризующих определенное болезненное состояние организма.Пример: Синдромное декодирование (7, 4)-кода Хэмминга.Используя (2.5) и (2.8), построим проверочную матрицу из порождающей матрицы кода Хэмминга (2.2). Она имеет видН3х7=/ 1 00 1 01 10 1 01 1 1 0\ 0 0 1 0 1 1 1(2.11)При передаче информационного слова и = (1010) по каналу без шума г = v = (0011010). Можем убедиться, что в этом случае синдромравен/ 1 00 10 01 1s =(0011010)©0 11 1001011=(000).(2.12)о \)Если, например, в кодовом слове произошла одиночная ошибка на2.3.
СиндромноедекодированиеТаблица 2.3. Таблица синдромов однократной ошибки (7,4)кода Хэмлинга.Кодовое слово гП)Г1Г2гзГАтъСиндром s100010001ПО011111re .101четвертой позиции (г = (0010010)), то синдромом является четвертаястрока транспонированной проверочной матрицы/ 1001s = (0010010) ©010 0 \1 00 11 01 11 1V1 0= (но).(2.13)1/Перебрав вес возможные позиции одиночной ошибки, получим полную таблицу синдромов однократных ошибок - таблицу соответствий номера ошибочного разряда получающемуся при этом синдрому (табл. 2.3). Можно заметить, что ошибке в г-ой позиции кодовогослова соответствует синдром, образованный г-ым столбцом матрицыН.
Так как все столбцы матрицы различны, мы можем с помощьютаблицы 2.3 исправлять одиночную ошибку, вносимую каналом.Обобщим приведенные выше рассуждения, используя аппаратлинейной алгебры.л- мерное двоичноевекторное пространство сарифметикой по модулю 2Рис. 2.3. Структура кодовых векторных пространств.Глава 2. Линейные блоковые кодыИсходным материалом для построения кодовых копструкций служит п -мерное двоичное векторное пространство, в котором заданыоперации арифметики по модулю 2 (табл. 2.2).В него вложено fc-мерное линейное пространство, содержащее 2ккодовых слов (рис. 2.3). Код С образуется с помощью 2 комбинацийклинейно независимых базисных векторов {gi, • • • ,g/t}- Иногдаговорят, что код С «натянут» на векторы {gi,... , gfc}.
Эти векторыобразуют строки порождающей матрицы кода Сgl#1,1 s i , 2 • • • g\,n02,1 52,2 • • • <?2,ng29k,2•••= (Pfcx(n-fc)-I*)-(2-14)9k,n)gfcЗаметим, что\ порождающаяматрица может быть разложена на матрицу Р и единичную матрицу I только в случае систематическихкодов.Для кода С существует дуальный код Сд такой, что скалярноепроизведение любой пары векторов, один из которых принадлежитпространству С, а другойпространству С^, всегда равно нулю.Это значит, что векторы кода С^ ортогональны векторам кода С. Сдругой стороны, если некоторый вектор ортогонален всем векторамкода С, то он принадлежит коду Cj, и наоборот.Дуальное векторное подпространство «натянуто» на.
п — к линейно независимые базисные векторы { h i , . . . ,h n _jt}- Эти векторыобразуют строки проверочной матрицыН (п—кух.п 'hih2\(2.15)К-к/—(In-fcпричем, правая часть равенства справедлива только для систематических кодов.При синдромном кодировании приемник использует свойство ортогональности кодовTG © H = O.(2.16)2.3. Синдромное декодирование I39JТаким образом, для каждого кодового слова v 6 С справедливоs = v © H T = O.(2.17)Каждому принятому слову, не принадлежащему коду, соответствуетотличный от нуля синдром8 =г©Нт/0дляг^С.(2.18)Проведем анализ синдромного декодирования на уровне двоичныхкомпонент (рис.
2.4). В канале производится покомпонентное сложение по модулю 2 кодового вектора v с двоичным вектором ошибки е.Таким образом, если г'-ая компонента вектора г равна «1», то в г-ойкомпоненте кодового вектора v возникает ошибка.В рассмотренном выше примере, единичной ошибке в четвертомразряде соответствует вектор е = (0001000).Замечание. Операция сложения по модулю 2 двоичных символовэквивалентна операции «исключающего или» XOR.Кодовое словоj^^Принятое словог = v®eКодерДекодериI•Информационноеслово•Шумовое словоДекодированноесловоР и с . 2.4. Модель передачи информацииуровне.на двоичномВ силу свойств линейности и ортогональности векторов имеемs =r © H T = ( v © e ) © H T =e © H T .(2.19)Последнее равенство является основой синдромного декодирования.В процессе декодирования могут возникнуть следующие ситуации:Случай 1: s = 0 •» е е ССлучай 1.1: е = 0 - безошибочная передача информации;Случай 1.2: е ф 0 - передача информации с неисправляемойошибкой;Глава 2.
Линейные блоковые кодыСлучай 2: s ^ О Ф> е ^ Сровании.ошибка будет обнаружена при декоди-Ясно, что в первом случае, декодер всегда выдает принятое слово г потребителю, при этом существует некоторая вероятность неисправления ошибки. Во втором случае возможны два режима работыдекодера.• Распознавание ошибок. Декодер всегда определяет наличие ошибки в принятом векторе г. В зависимости от требований потребителя, принятое информационное слово или «стирается», илипроизводится запрос на его повторную передачу.• Коррекция ошибок.
Корректирующая способность декодера может быть пояснена на примере (7,4)-кода Хэмминга, рассмотренного выше.Таблица 2.3 показывает, что в случае одночной ошибки, ее позиция однозначно определяется по синдрому, и, таким образом, однократная ошибка всегда исправляется. Ошибки же большей кратности декодер всегда исправляет как одиночные, и потребителю выдается ошибочное информационное слово. Пусть, например, передается кодовое слово ,v = (0011010), соответствующее информационномувектору и = (1010), и вектор ошибки равен е = (1100000), т.е. вканале произошла двукратная ошибка. Тогда для принятого словаг = (1111010) синдром равен s = (110).
Из табл. 2.3 следует, что этотсиндром соответствует четвёртой ошибочной компоненте вектора г.Таким образом, потребителю будет выдан вектор й = (0010).Декодер может выдавать потребителю ошибочное информационное слово тогда и только тогда, когда в канале произошли необнаружимые ошибки, или кратность канальной ошибки превышает корректирующую способность кода. Из рассмотренного выше примераследует, что эффективность конкретного кода зависит от областиего применения и, в особенности, от канала, связи. Если мы передаем информацию по каналу с аддитивным белым гауссовским шумом(АБГШ), то ошибки в кодовом слове независимы. Если при этом отношение сигнал/шум достаточно велико, то вероятность одиночнойошибки во много раз превышает вероятность ошибок высших кратностей, поэтому, использование в таком канале кода Хэмминга с исправлением однократной ошибки может оказаться весьма эффективным.
С другой стороны, в каналах, где преобладают многократные2.4- Свойства линейных блоковых кодовошибки (например, в каналах с замираниями), исправление одиночных ошибок лишено смысла. При практическом выборе конкретногопомехоустойчивого кода необходимо также учитывать скорость егодекодирования и сложность технической реализации.2.4. Свойства линейных блоковых кодовВ предыдущих разделах на примере (7,4)-кода Хэмминга были показаны основные свойства линейных блоковых кодов и приведен методсиндромного декодирования. Теперь возникает следующий вопрос:Чем отличаются «хорошие» коды от «плохих» и как их искать? Вследующих параграфах, раскрывая структуру линейных кодов болееподробно, мы постараемся коротко сформулировать ответ на этот вопрос.2.^.1.
Расстояние Хэмминга и корректирующаяспособностьДля лучшего понимания процесса декодирования будем использовать геометрическое представление векторного пространства. Нарис. 2.5 показан сектор n-мерного двоичного векторного пространства. В нем особое место занимает я-мерный кодовый вектор 0, который всегда принадлежит любому линейному коду (это следует изсвойств линейных кодов). Здесь же показаны п-мерные кодовые векторы vi,v2,V3, обозначенные символами «о». Возможные принимаемые векторы г обозначены символами «х». Области декодированиякодовых слов vi,уз, V3 показаны как окружности с центрами в точках, соответствующих изображениям этих кодовых слов на плоскости. Это значит, что если принятый вектор г находится, например,внутри затемненной области (рис. 2.5), то декодер выдаст потреби1телю кодовое слово vi.Пусть в канал посылается слово vi.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
