Васюков В.Н. - Теория электрическо связи - Часть 3. Теория информации и теория помехоустойчивости (1275348), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Если для некоторой пары векторов скалярное произведение равно 0, то векторы являются ортогональными.Таким образом, множество всех двоичных кодовых слов длины nможно рассматривать, как n -мерное линейное пространство над конечнымполем скаляров GF (2) . Хотя это пространство содержит лишь конечноемножество векторов, а именно 2n , оно удовлетворяет всем аксиомам векторного пространства [4, 5].Линейные коды являются разделимыми, поэтому из n символов толькоk являются информационными, а остальные ( n − k ) – проверочными.

Тогда,очевидно, в n -мерном пространстве Sn всех комбинаций можно выделитьk -мерное подпространство Sk разрешенных комбинаций. Таким образом,пространство Sn можно представить прямой суммой k -мерного подпространства Sk и ( n − k )-мерного подпространства Sn − k , так что любой векториз Sn − k ортогонален любому вектору, принадлежащему Sk :Sn = Sk ⊕ Sn − k , Sk ⊥ Sn − k ,где ⊕ – символ прямой суммы, а знак ⊥ обозначает ортогональность подпространств.Предположим, что блок из k информационных двоичных символовкодируется словом из n канальных двоичных символов.

Обозначим информационный k -мерный вектор7 через X = ( x1,..., xk ) , кодовый n -мерный вектор через C = (c1,..., cn ) . Кодирование описывается линейным преобразованием (оператором), отображающим векторы, принадлежащие подпространствуSk , в векторы из SnC = XG ,(8)где G – матрица кодирования (порождающая матрица кода) вида7В кодировании принято записывать векторы, как вектор-строки.30 g11g 21 .G = . . g k1g12g 22..................gk 2...g1n g 2n .

.. . g kn Уравнение (8) можно рассматривать и как систему из n линейныхуравнений видаc j = x1g1 j + x2 g 2 j + ... + xk g kj , j = 1,..., n ,где сложение понимается по модулю 2.Нетрудно видеть, что любое кодовое слово – это не что иное, как линейная комбинация строк матрицы G с весовыми коэффициентами, равнымиинформационным символам. Отсюда следует, что, хотя разрешенные кодовые слова принадлежат всему пространству Sn , они также принадлежат k мерному подпространству Sk , натянутому на векторы – строки матрицы G ,какова бы ни была эта матрица (если, конечно, у нее n столбцов и k строк,которые, очевидно, должны быть линейно независимыми). Путем линейныхопераций над строками и перестановки столбцов любую такую матрицуможно привести к систематическому виду1 0 00 1 0.

. .G = ( Ik # P ) = . . .. . .0 0 0............0 p110 p21. .. .. .1 pk1p12.p22 .......pk 2 .p1( n − k ) p2( n − k ) .. ,..pk ( n − k ) (9)где I k – единичная матрица размера k × k , а P – матрица размера k × (n − k) .Воздействие такого преобразования на информационный вектор приводит кформированию кодового вектора, k первых символов которого повторяютсимволы информационного вектора, а остальные (n − k ) символов формиру31ются из информационных матрицей P и являются проверочными (паритетными). В этом случае код называют систематическим. Любой линейный кодможно преобразованием матрицы привести к систематическому коду, эквивалентному в смысле помехоустойчивости, которая определяется расстояниями между кодовыми словами, инвариантными к таким преобразованиям.Все порождающие матрицы эквивалентных кодов представляют собой наборы векторов-строк, являющимися различными базисами одного и того жеподпространства.Пример 6.

Систематический код (7,4) порождается матрицей10G =000 0 0 1 0 11 0 0 1 1 1 .0 1 0 1 1 00 0 1 0 1 1Кодовые слова имеют структуру C = ( x1, x2 , x3 , x4 , c5 , c6 , c7 ) , гдеc5 = x1 + x2 + x3 ,c5 = x2 + x3 + x4 ,c5 = x1 + x2 + x4(подразумевается сложение по модулю 2).Реализовать такое кодирование можно при помощи устройства, структурная схема которого приведена на рис. 3.Устройство включает два сдвиговых регистра на 4 и 3 разряда, а такжетри сумматора по модулю 2.

Информационная последовательность поступаетна вход первого регистра и записывается в его разрядах. На выходах сумматоров по модулю 2 формируются проверочные символы, которые запоминаются в разрядах второго сдвигового регистра. Последним шагом формирования кода является считывание вначале четырех информационных символов, азатем – проверочных, при этом на выходе устройства получается семиразрядное кодовое слово. ♦32xx4x3x2x1Выходc7c6c5Рис.

3. Структура кодера для систематического кода (7,4)Применение любого кода предполагает достаточно простую реализацию не только кодирования, но и декодирования. Декодирование систематического линейного блочного кода могло бы заключаться в простом отбрасывании проверочных символов, но это не обеспечивало бы обнаружения и исправления ошибок.Вернемся к структуре пространства Sn . Подпространство Sk представляет собой множество всех разрешенных кодовых комбинаций – линейнуюоболочку совокупности вектор-строк порождающей матрицы G . Другимисловами, подпространство Sk и есть код (n, k ) . Тогда подпространство Sn − k ,ортогональное к нему, также можно считать некоторым кодом (n, n − k ) , дуальным к данному. Порождающая матрица H дуального кода содержит(n − k ) линейно-независимых строк длины n .Любое кодовое слово (n, k ) -кода ортогонально любому кодовому слову(n, n − k ) -кода, следовательно,GH T = 0 ,где 0 – матрица размера k × (n − k ) , состоящая из нулей, (⋅)T – символ транспонирования.

С учетом (9) можно записать()H = −PT # I n −k ,33(10)причем для двоичного кода минус можно опустить, так как сложение и вычитание по модулю 2 совпадают.Матрица H является порождающей матрицей дуального кода; в то жевремя она может использоваться для обнаружения ошибок.

В самом деле, если принятая кодовая комбинация Y является разрешенной, то она ортогональна к подпространству Sn − k , или, что то же самое, ко всем строкам матGGрицы H , поэтому YH T = 0 , где 0 – нулевой вектор размерности (n − k ) . Таким образом, умножая слева вектор-строку, соответствующую принятойкомбинации, на транспонированную матрицу H T , получаем вектор (называемый синдромом), который равен нулевому вектору в том и только в томслучае, если комбинация является разрешенной. В противном случае комбинация является запрещенной, следовательно, при передаче произошла ошибка. По значению синдрома можно определить, какой именно разряд кодовогослова содержит ошибку.Коды Хэмминга.Одним из наиболее известных классов помехоустойчивых линейныхблочных кодов являются коды Хэмминга.

Коды Хэмминга представляют собой (n, k ) -коды, удовлетворяющие условию(n, k ) = (2m − 1,2m − 1 − m)при некотором целом m .В частности, рассмотренный (7,4)-код является кодом Хэмминга.Особое свойство кодов Хэмминга заключается в строении проверочнойматрицы. Для любого линейного кода проверочная матрица содержит (n − k )строк и n столбцов; для кода Хэмминга n = 2m − 1 и проверочная матрицасодержит в качестве столбцов все возможные комбинации нулей и единиц,исключая нулевой вектор.Для кода (7,4), рассмотренного в примере 6, проверочная матрица в соответствии с выражением (10), очевидно, имеет вид34 1 1 1 0 1 0 0H =  0 1 1 1 0 1 0  .1 1 0 1 0 0 1Если передается кодовая комбинация C и в канале происходит ее искажение, то принятую комбинацию Y можно представить в виде Y = C + e ,где e – вектор ошибки, содержащий единичные компоненты в тех позициях,в которых произошли ошибки, то есть нули были заменены единицами илинаоборот (напомним, что суммирование всюду понимается по модулю 2).Умножим принятую комбинацию на транспонированную проверочнуюматрицуGYH T = CH T + eH T = 0 + eH T = у ,здесь вектор у представляет собой синдром, который равен нулевому вектору в том и только в том случае, если вектор ошибки ортогонален всем строкам проверочной матрицы, то есть подпространству Sn − k .

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

Предположимтакже, что при передаче произошла ошибка, скажем, во втором символе, такчто принята комбинация 0000111.Умножая вектор-строку, соответствующую принятой комбинации, слева на транспонированную проверочную матрицу H T , получим синдром35111( 0 0 0 0 1 1 1)  0100010101011 01  = (1 1 1) ,001 который совпадает со второй строкой матрицы H T . Это указывает на то, чтоошибочным является второй символ принятой комбинации. ♦То обстоятельство, что синдром позволяет определить номер «испорченного» символа, фактически означает возможность исправления ошибок. Всамом деле, если точно известно, что во втором символе имела место ошибка, декодер может ее исправить, прибавив (по модулю 2) к ошибочному символу единицу. Поэтому код Хэмминга принадлежит к кодам, исправляющимошибки, или корректирующим.Границы корректирующей способности кода Хэмминга иллюстрируются следующим примером.Пример 8.

Предположим, что при передаче разрешенной кодовой ком-бинации 0100111 произошли две ошибки, скажем, в третьем и пятом символах, так что принята комбинация 0110011. Найдем синдром:111( 0 1 1 0 0 1 1)  0100011101011 01  = ( 0 1 0) .001 Синдром указывает на 6-й символ, как на ошибочный. Таким образом,в случае двукратной ошибки факт ошибки обнаруживается (синдром оказывается ненулевым), но исправить ошибку нельзя, так как синдром оказывается таким же, как в случае однократной ошибки в другом символе. Итак, код36Хэмминга (7,4) обнаруживает одно- и двукратные ошибки и исправляет однократные.

♦Помехоустойчивость рассмотренного кода Хэмминга просто объясняется с геометрической точки зрения. Легко убедиться, что расстояние междулюбыми двумя разрешенными комбинациями этого кода не менее 3. Поэтомупри приёме запрещенной комбинации она заменяется той разрешенной комбинацией, расстояние до которой равно 1. Двукратная ошибка отдаляет принимаемую комбинацию на расстояние, равное 2, что и приводит к ошибочному «исправлению» ошибки. При этом «исправляется» один символ, поэтому «исправленная» комбинация отстоит от принятой на расстояние 1.Упражнения.1. Найдите две разрешенные кодовые комбинации кода Хэмминга(7,4), не совпадающие со строками порождающей матрицы, и убедитесь втом, что расстояние между ними не менее трех.2. Измените в одной из комбинаций два символа, найдите синдром и«исправьте» в принятой комбинации символ, на который он укажет.

Характеристики

Список файлов книги