Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
(=0
л + к
f'(D)= 2 ifiD1-1. i= 1
Коэффициент i в приведенном выше выражении может интерпретироваться как г'-кратная сумма единиц, так что, быть может, более ясной является запись
л+ к
f(D)= 2 Rp(i)fiD‘-\ i=о
651
где Rp(i) интерпретируется как целый элемент поля GF(pm). Здесь суммирование распространено до г = 0, так как соответствующее слагаемое равно 0. Можно выразить каждый из коэффициентов fj через коэффициенты g(D) и h(D):
i
fi~ 2 Bjhi-j,
/=о
n-j- k i
f'(D)= 2 *p(0 2 Sjhi-J D‘~ 1 .
i=o i=о
Заметив, что суммирование приведенной выше двойной суммы производится по всем / < (, меняем порядок суммирования, просуммировав по всем i > /:
n-j-к n-j-k
f'(D)= 2 2 RpWgjhi-jD1-1^
i=o i=i
rt tt + k
= 22 RpWgjhi-jD1-'. j = 0 ( = /
В последнем равенстве использовано то, что gj = 0 при j > п. Теперь положим / = i — j и заменим сумму по i суммой по I:
Г(Р)= 2 ”+2 ‘RpU + nejbiDi+t-1.
/= о г = о
Так как / <яи hi равно 0 при / > к, то во второй сумме суммирование необходимо произвести лишь до I = k:
п к
f'(D)= 2 2 [RpU) + Rp(WeihiDl+i~x =
j = о 1 = 0
= 2 2 RP (/) Sj1 hi Dl+ 2 2 RP W Si D1' hiDl~x = j=01=0 j=0l=0
=g' (D)h(D) + g(D)h‘ (D).
Использовав этот результат несколько раз, получим
a'(D) = [ri(l_i/yD)j/=[l-i/1D]'(1 -UjD) +
+ (1—i/i D) Г П (1-UjD)]' ^[1-UxDV П (1 -UjD) +
[/>1 J />1
+ (l—U1D)[l—UtD]' П (i-UjD) + (l-U1D)(l-U2D). i> i
• Г П (1 -UjD)V= ... = 2 [ 1-UtDV П (l-UjD)=>
L />2 J i=\
e
= - 2 Vi П (1 -UjD).
i = I / Ф i
6.37. Представленный здесь кодер можно исследовать так же, как был исследован кодер рис. 6.8.1. Следующие синдромы содержат г^1*:
51 = 2<i2> ©г*!1»,
52 = г<22>©2П>0г<Л
S5 = z(62> ®г<6‘) фг!1» 0г1», (1)
S,=2(,2) фг^1» ®г<4 ®г<” ф2<".
Заметим, что эти четыре линейные комбинации шумовых символов уже ортогональны к г(11> и потому представленный ниже декодер может исправлять всё пары ошибок.
Коды подобного типа, у которых синдромы, проверяющие г*}1, ортогональны к г*}*, известны под названием самоортогональных кодов. Интересная особенность таких кодов состоит в том, что линия обратной связи может быть опуще-
на. Это позволяет избежать проблемы распространения ошибок. Чтобы убедиться в этом, просто перепишем четыре равенства (1), включив в них те ошибочные символы, которые уже прошли через декодер. Тогда можно убедиться, что получившиеся линейные комбинации, содержащие также уже исправленные символы, все еще ортогональные к г^’- Такое декодирование, не использующее линию обратной связи, называется определенным декодированием (см. Robinson J. P., IEEE Trans., IT—14, 121 — 128, January 1968).
6.38. Проведя то же самое исследование, что и при рассмотрении кодера, представленного на рис. 6.8. 1, получим:
s1=42) ©41'’ sT=z^©4,)e41).
s8=42) ©41’ ® 4” ©4!)>
/, если 3 вхтЫгх f, если «¦ или S &xo<?hi>/x
символа равпы1 символов pct&xwf
653
Первые четыре приведенных выше комбинации ортогональны к г1};', а последняя может быть включено в это множество, если сложить ее с S4 и S2:
Тогда декодер имеет вид, представленный на рисунке выше.
6.39. (а) Как показано на стр. 248, дуальным кодом к коду максимальной длины служит код Хэмминга и каждое кодовое слово в дуальном коде является проверочным соотношением в первоначальном коде (т. е. если h = (/г0, hlt ..., hN_{) является кодовым словом дуального кода, то для любого кодового слова х =
= (х0....xN__ 1) первоначального кода выполняется соотношение x0h0 ©
© xi^i © © xn— 1 hN_i = 0). Напомним теперь, что минимальное расстоя-
ние в коде Хэмминга равно 3 и что любая двоичная последовательность из N символов отличается от ближайшего кодового слова не более чем в одной позиции. Поэтому при любом г, 0 -< г < N — 1, можно считать, что в последовательности из N символов на i-й и (7V — 1)-й позициях находится единица, а на остальных позициях — нули. Эта последовательность должна отличаться в одной позиции в точности от одного кодового слова кода Хэмминга и это кодовое слово должно содержать 3 единицы. Поэтому для каждого /, 0 < г < N — 1 существует единственное /, 0 < / < N — 1, такое, что последовательность, содержащая единицы в г'-й, /-й и (N— 1)-й позициях и с нулями в остальных позициях, является кодовым словом кода Хэмминга. Число таких пар (/, /) равно (N—1)/2 и каждая из них соответствует одному уравнению из множества (N — 1)/2 проверочных уравнений кода максимальной длины. Эти проверочные уравнения дают (N — 1)/2 линейных комбинаций шумовых символов, ортогональных к гд,_].
