Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
(г) Из пункта (в) при i — 0 следует, то существуют <7 кодовых слов, символы которых равны нулю для любой заданной совокупности N — dmin позиций. Одно из них нулевое кодовое слово, а другие должны быть ненулевыми в остальных dmin позициях (так как ни одно ненулевое кодовое слово не может иметь вес,
6.32. Так как а — примитивный элемент, то длина блока в коде равна 2m — 1 и порождающий многочлен имеет степень т. Поскольку все единичные ошибки могут быть исправлены и число проверочных символов равно т, то код должен быть кодом Хэмминга. Соотношение (6.7.27) при d = 3 имеет вид
Так как а0 всегда равно 1, то = — Si/S0 (или при отсутствии ошибок = = 0). При одной ошибке, например в лх-й позиции, S0 = a"1, Sj = (ал‘)2 и, следовательно,
Это решение для o(D) = а0 + oxD позволяет найти пх по и, следовательно, исправить ошибку. Таблица декодирования в данном случае, по существу, эквивалентна нахождению пх по
6.33. PCJIOC минимальной длины для 1 + D3 + D* + D1- имеет вид, изображенный на рисунке.
меньший dmin)- Число таких заданных совокупностей р; вательно, в коде Рида-Соломона вес dmin имеют (q — 1)
следо-
Oi = —ап‘
649
Первоначально в регистре хранятся представленные на рисунке символы, а на выходе вначале появляется постоянный член, т. е. 1, затем коэффициент при D, т. е. О, затем коэффициент при D2, т. е. О и т. д. РСЛОС минимальной длины для D2 + D5 + De изображена на рисунке, на котором указаны символы, находящиеся в регистре в начальный момент.
6.34. Существует много способов выполнения этого. Приведенная здесь блок-схема, по-видимому, является простейшей по идее, хотя и не самой простой при осуществлении.
Содержимое после поступления !5 символов
5О
S5
Все регистры сдвига первоначально незаполнены; затем поступает уд,_ь после чего каждый регистр сдвигается вправо указанное число раз. По окончании этих сдвигов в г-м регистре будет храниться величина yN_x& , представленная в виде многочлена, у которого члены высшего порядка находятся справа. После этого поступает yN_2 и регистры вновь сдвигаются, после чего в г-м регистре остается у^—\ + Уы—2а‘ • После того как поступит, наконец, у0 и будут
проведены сдвиги, то в г-м регистре будет у(а1) = S^_p что и требовалось.
6.35. Алгоритм для An(D) определяется соотношением
An+1(D)=An(D)~ 4r-Dn~kn Ak (D); n> 1, (1)
n
с начальными условиями A0(D) = 0, A-i(-D) = —D~l. Нужно показать, что при каждом п > 0, определенное выше An(D) равно
An(D) = [Cn(D)S (?»)]?-'. (2)
Заметим, что (2) справедливо при п = 0, так как обе части (2) равны 0. Теперь воспользуемся индукцией. Предположим, что (2) выполняется для (D), А2 (D), ..., An(D) и покажем, что это соотношение справедливо для Лп+хф). Используя (6.7.36), получаем
650
Сдвиги, регистра „ на входящим, символ 1
[Cn+1 (D) S (D)ti-=lCn (D) S (D)]n0-
-~Dn k*Ck {D)S(D)
hr, n
Подставляя значения dn [см. (6.7.34)] в первое из приведенных выше слагаемых
и вынося Dn~~kn за скобки справа (заметим, что это требует уменьшения верх-
него индекса скобки на и — кп), получаем
[Cn+1 (D) S (?>)]? = [С„ (D) S (D)]n,~ 1 +
+ dn Df1 Dn~ hn \Ckn (D) S (D)j kn . (3)
kn
Рассмотрим отдельно случай kn > 0 и kn = — 1.
Случай 1. kn > 0.
По определению dk ,
(D) S (D)f- = [C,n (D) S (D)]kQn~ * +dhn Dk» .
Подставляя это в (3) и сокращая подобные члены, получаем [Сп+1 (D) S (D)]n0 = [Сп (D) S (D)]n0~1 — Dn~kn S (?>)]
71
В силу предположений индукции соотношение (2) справедливо для каждого из стоящих справа слагаемых, так что
[C„+1 (D) S (D))n0=An (D)— Dn~kn Ak (D) =Лп+1 (D).
[в силу (1)].
Случай 2. kn = — 1.
В этом случае правое слагаемое в (3) равно 0, так что
[Cn+1 (D) S (D)B =[Cn (D) S (D))n0~1 +dn Dn. (4)
Напомним, что при kn = — 1 имеем dk =1, Ак (D) = —D-1, поэтому
dnDn==_^L.Dn-knA (D) для kn = -1. (5)
dk п ап
Подставляя (5) в (4) и используя (2) в предположениях индукции, получаем {Cn+i(D)S(D)\n0=An(D)--^Dn-kn Ak (D)=An+1(D)
Ч
[в силу (1)].
Таким образом показано, что (2) справедливо при п + 1, что завершает доказательство.
6.36. Пусть f(D) = g(D) h(D), где g(D) — многочлен п-й степени над GF(pm),
n-\-k
a h(D) — многочлен k-й степени над GF(pm). Полагая f(D) = 2 fiD1, имеем
