Вернер М. Основы кодирования (2004) (1151849), страница 18
Текст из файла (страница 18)
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. В результате искажения в канале могут иметь место три варианта приема и декодирования (рис. 2.5).• В первом случае, вектор ошибки ei отображает переданныйвектор в точку, принадлежащую области декодирования vi.Декодер выдает потребителю переданное слово vi, исправляяпри этом возникающие в канале ошибки.Представление n-мерных векторов точками на плоскости не должно смущатьчитателя, т.к. такое наглядное описание кодов позволяет только лучше понятьих свойства и никакой другой цели перед собой не ставит.
Прим. перев.142Глава 2. Линейные блоковые кодыВо втором случае, вектор ег переводит переданный вектор viв область декодирования V2. Таким образом, потребителю выдается ошибочное слово V2 вместо vi. Тем не менее, ошибкараспознается, так как принятый вектор Г2 не является кодовым словом.В третьем случае, вектор ошибки ез отображает переданноеслово в ошибочное кодовое слово V3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
