В.Н. Васюков - Теория электрической связи (1266498), страница 40

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

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

Хотя это пространство содержитлишь конечное множество векторов, а именно 2n , оно удовлетворяет всем аксиомам векторного пространства [2].Линейные коды являются разделимыми, поэтому из 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 -мерныйОбозначим информационныйвектор109 черезX  ( x1,..., xk ) , кодовый n -мерный вектор через C  (c1,..., cn ) .

Ко109В кодировании принято записывать векторы, как векторы-строки.2488. ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИдирование описывается линейным преобразованием (оператором),отображающим векторы, принадлежащие подпространству Sk , ввекторы из SnC = XG ,(8.9)где G – матрица кодирования (порождающая матрица кода) вида g11g 21 .G. .g k1g12g 22...gk 2..................g1n g2n . .. .

g kn Уравнение (8.9) можно рассматривать и как систему из n линейных уравнений видаc j  x1 g1 j  x2 g 2 j  ...  xk g kj , j  1,..., n ,где сложение понимается по модулю 2.Нетрудно видеть, что любое кодовое слово – это не что иное,как линейная комбинация строк матрицы G с весовыми коэффициентами, равными информационным символам. Отсюда следует,что, хотя разрешенные кодовые слова принадлежат всему пространству Sn , они также принадлежат k -мерному подпространству Sk , натянутому на векторы – строки матрицы G , какова бы нибыла эта матрица (если, конечно, у нее n столбцов и k строк, которые, очевидно, должны быть линейно независимыми). Путемлинейных операций над строками и перестановки столбцов любуютакую матрицу можно привести к систематическому виду:G  I k1 0 00 1 0.

. . P  . . .. . . 0 0 0............0 p110 p21. .. .. .1 pk1p12.p22....pk 2....p1( n  k ) p2( n  k ) .. , (8.10)..pk ( n  k ) 8.5. Помехоустойчивое кодирование249где Ik – единичная матрица размера k  k , а P – матрица размераk  (n  k ) . Воздействие такого преобразования на информационный вектор приводит к формированию кодового вектора, k первых символов которого повторяют символы информационноговектора, а остальные ( n  k ) символов формируются из информационных матрицей P и являются проверочными (паритетными).В этом случае код называют систематическим. Любой линейныйкод можно преобразованием матрицы привести к систематическому коду, эквивалентному в смысле помехоустойчивости, котораяопределяется расстояниями между кодовыми словами, инвариантными к таким преобразованиям.

Все порождающие матрицы эквивалентных кодов представляют собой наборы векторов-строк, являющиеся различными базисами одного и того жеподпространства.Пример 8.7. Систематический (7, 4)-код порождается матрицей1 0 0 0 1 0 10 1 0 0 1 1 1.G0 0 1 0 1 1 0 0 0 0 1 0 1 1 гдеКодовые слова имеют структуру C  ( x1, x2 , x3 , x4 , c5 , c6 , c7 ) ,c5  x1  x2  x3 ,c6  x2  x3  x4 ,c7  x1  x2  x4(подразумевается сложение по модулю 2).Реализовать такое кодирование можно при помощи устройства,структурная схема которого показана на рис.

8.2.Устройство включает два сдвиговых регистра объемом 4 и3 разряда, а также три сумматора по модулю 2. Информационнаяпоследовательность поступает на вход первого регистра и записывается в его разрядах. На выходах сумматоров по модулю 2 формируются проверочные символы, которые запоминаются в разрядах второго сдвигового регистра. Последним шагом формированиякода является считывание вначале четырех информационных символов, а затем – трех проверочных, при этом на выходе устройстваполучается семиразрядное кодовое слово. ◄2508. ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИхxx3x4x1x2Выходс7с6с5Рис.

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

С учетом (8.10) можно записатьH   PT  I nk ,(8.11)причем для двоичного кода минус можно опустить, так как сложение и вычитание по модулю 2 совпадают.Матрица H является порождающей матрицей дуального кода;в то же время она может использоваться для обнаружения ошибок.В самом деле, если принятая кодовая комбинация Y является раз-8.5. Помехоустойчивое кодирование251решенной, то она ортогональна к подпространству110 Snk , или,что то же самое, ко всем строкам матрицы H , поэтому YHT = 0 ,где 0 – нулевой вектор размерности ( n  k ) . Таким образом, умножая слева вектор-строку, соответствующую принятой комбинации, на транспонированную матрицу HT , получаем вектор (называемый синдромом), который равен нулевому вектору в том итолько в том случае, если комбинация является разрешенной.В противном случае комбинация является запрещенной, следовательно, при передаче произошла ошибка.

По значению синдромаможно определить, какой именно разряд кодового слова содержитошибку.Коды ХэммингаОдним из наиболее известных классов помехоустойчивых линейных блочных кодов являются коды Хэмминга. Коды Хэммингапредставляют собой (n, k ) -коды, удовлетворяющие условию(n, k )  (2m  1,2m  1  m)при некотором целом m .В частности, рассмотренный (7, 4)-код является кодом Хэмминга.Особое свойство кодов Хэмминга заключается в строении проверочной матрицы. Для любого линейного кода проверочная матрица содержит ( n  k ) строк и n столбцов; для кода Хэммингаn  2m  1 и проверочная матрица содержит в качестве столбцоввсе возможные комбинации нулей и единиц, исключая нулевойвектор.Для (7, 4)-кода, рассмотренного в примере 8.7, проверочнаяматрица в соответствии с выражением (8.11), очевидно, имеет вид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 – вектор ошибки, содержащий единичные110Это подпространство также называют нуль-пространством [15].2528.

ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИкомпоненты в тех позициях, в которых произошли ошибки, т. е.нули были заменены единицами или наоборот (напомним, чтосуммирование всюду понимается по модулю 2).Умножим принятую комбинацию на транспонированную проверочную матрицуYHT = CHT + eHT = 0 + eHT = σ ,здесь вектор σ представляет собой синдром, который равен нулевому вектору в том и только в том случае, если вектор ошибки ортогонален всем строкам проверочной матрицы, т.

е. подпространству Snk . Это означает, что не могут быть обнаружены ошибки,составляющие вектор, который сам является разрешенной комбинацией кода.Чтобы убедиться в корректирующих свойствах кода Хэмминга,рассмотрим пример обнаружения ошибки в кодовой комбинации.Пример 8.8. Предположим, что передавалась разрешенная кодовая комбинация 0100111 (напомним, что разрешенными комбинациями являются все линейные комбинации строк порождающейматрицы кода). Предположим также, что при передаче произошлаошибка, скажем, во втором символе, так что принята комбинация0000111.Умножая вектор-строку, соответствующую принятой комбинации, слева на транспонированную проверочную матрицу HT , получим синдром1110 0 0 0 1 1 1  010 001110101101   1 1 1 ,00 1 который совпадает со второй строкой матрицы HT . Это указываетна то, что ошибочным является второй символ принятой комбинации.

◄То обстоятельство, что синдром позволяет определить номер«испорченного» символа, фактически означает возможность исправления ошибок. В самом деле, если точно известно, что во вто-2538.5. Помехоустойчивое кодированиером символе имела место ошибка, декодер может ее исправить,прибавив (по модулю 2) к ошибочному символу единицу. Поэтомукод Хэмминга принадлежит к кодам, исправляющим ошибки, иликорректирующим.Границы корректирующей способности кода Хэмминга иллюстрируются следующим примером.Пример 8.9.

Предположим, что при передаче разрешенной кодовой комбинации 0100111 произошли две ошибки, скажем, втретьем и пятом символах, так что принята комбинация 0110011.Найдем синдром:1110 1 1 0 0 1 1  010 001110101101   0 1 0  .001 Синдром указывает на 6-й символ, как на ошибочный. Такимобразом, в случае двукратной ошибки факт ошибки обнаруживается (синдром оказывается ненулевым), но исправить ее нельзя, таккак синдром оказывается таким же, как в случае однократнойошибки в другом символе. Итак, код Хэмминга (7,4) обнаруживаетодно- и двукратные ошибки и исправляет однократные.

◄Помехоустойчивость рассмотренного кода Хэмминга простообъясняется с геометрической точки зрения. Легко убедиться, чторасстояние между любыми двумя разрешенными комбинациямиэтого кода не менее 3. Поэтому при приеме запрещенной комбинации она заменяется той разрешенной комбинацией, расстояние докоторой равно 1. Двукратная ошибка отдаляет принимаемую комбинацию на расстояние, равное 2, что и приводит к ошибочному«исправлению» ошибки. При этом «исправляется» один символ,поэтому «исправленная» комбинация отстоит от принятой на расстояние 1.Коды, обнаруживающие ошибки, но не исправляющие их, могут использоваться в системах с решающей обратной связью (системах с переспросом [10]).

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

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