Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
L
O = jS*zftin0*n; L<n<N. (6.1.10)
Путем сравнения этого равенства с матрицей на рис. 6.1.3 нетрудно убедиться, что оно может быть переписано в следующей матричной форме: для каждого кодового слова х
хЯ = 0. (6.1.11)
Обратно, если произвольная последовательность х удовлетворяет соотношению (6.1.11), она также удовлетворяет (6.1.9). Эта последовательность должна быть кодовым словом, соответствующим инфор-
215
N-L
н-
мационной последовательности, определяемой первыми L символами вектора х. Таким образом, множество кодовых слов — это множество последовательностей х, для которых хН = 0 (т. е. нуль в пространстве столбцов матрицы Я); множество кодовых слов является также множеством линейных комбинаций строк G (т. е. пространством строк матрицы G).
Матрица Я используется в основном для декодирования. Пусть при передаче по двоичному каналу используется некоторый заданный систематический код с проверкой на четность, и у — принятая последовательность; определим соответствующий у синдром S равенством
S = у Я. (6.1.12)
Синдром S — это вектор-строка (Slt ..., Sn-l) с N—L компонентами, по одной для каждого проверочного символа. Поскольку
L
$i = 2 Ulgl,L + i® tjL + l ,
Hl+1 I
$Z,L + 1
$L,L + 1 N
1 0 0.......0
О Г о.......О
0 о О ....... 1
Рис. 6.1.3.
то нетрудно убедиться, что 5, равно 1 тогда и только тогда, когда принятый г-й проверочный символ yL+i отличается от г'-ro проверочного символа, вычисленного по принятым информационным символам. Отметим, что если хт является каким-либо кодовым словом, то
(у ®хт)Н = уН ®хтН = S.
(6.1.13)
Если хт—переданный, а у — принятый вектор, то последовательность у 0 хт, содержит 1 на тех позициях, на которых отличаются у и хт. Эта последовательность называется шумовой последовательностью гт, соответствующей хт; из (6.1.13) получаем
гтН
S.
(6.1.14)
Так как хЯ = 0, тогда и только тогда, когда х кодовое слово, из (6.1.13) следует, что для выполнения соотношения гН = S необходимо и достаточно, чтобы г была одной из определенных выше шумовых последовательностей.
Нужно отметить, что соотношение (6.1.14) не позволяет точно установить, какая шумовая последовательность действительно имела место при передаче. Оно представляет собой соотношение, справедливое для всех М — 2L возможных последовательностей ошибок, соответствующих М кодовым словам. Выбор zm (или выбор кодового слова) зависит от канала.
216
Предположим теперь, что при передаче по ДСК (см. рис. 5.3.1, а) с переходной вероятностью е < 1/2 используется систематический код с проверкой на четность. Тогда, если кодовое слово хт и принятая последовательность у отличаются в е позициях, то Рг(у|хт) = = ее (1 — e)N~e. Число позиций, в которых отличаются две двоичные последовательности, называется расстоянием Хэмминга между этими последовательностями. Нетрудно видеть, что Pr(y|xm) — убывающая функция от расстояния Хэмминга между у и хт, и поэтому декодирование по максимуму правдоподобия эквивалентно выбору кодового слова, находящегося на минимальном расстоянии от у. Отметим также, что расстояние между у и хт равно числу единиц (называемому весом) в шумовой последовательности ът = у@хш. Декодирование по максимуму правдоподобия состоит в выборе кодового слова хт, для которого zm = yQxm имеет минимальный вес. Эти результаты можно сформулировать в виде следующей теоремы.
Теорема 6.1.1. Пусть систематический код с проверкой на четность имеет проверочную матрицу Я и пусть этот код используется в ДСК с переходной вероятностью е < 1/2. Тогда при заданной принятой последовательности у декодирование по максимуму правдоподобия состоит в вычислении синдрома S == у Я, нахождении среди последовательностей, удовлетворяющих соотношению S = zH, последовательности z с минимальным весом и декодировании кодового слова х = z 0 у.
Таблицы декодирования
Доказанная теорема оставляет нерешенной задачу нахождения решения уравнения S = гН, которое обладает минимальным весом. Один из путей решения этой задачи основан на таблице декодирования. Мы можем составить список из 2N~L возможных значений S и каждому из них поставить в соответствие последовательность z с минимальным весом. Проще всего реализовать эту идею, если начать с последовательностей нулевого веса, затем составить список всех z, обладающих единичным весом, затем весом 2 и т. д. Для каждого из z можно вычислить синдром S ~ zH и, если в дальнейшем в списке появится уже вычисленный синдром S, то соответствующий ему новый вектор z опускается. Составление таблицы заканчивается, как только все возможные 2N~L векторов S появятся в таблице. На рис. 6.1.4 представлена такая таблица декодирования для кода, приведенного на рис. 6.1.1.
