Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
6.21. Доказательство 1. Если g0 = 0, то многочлен gmDm~l + 8т—1 Dm~2+ + ... + gt является циклическим сдвигом g(D) и потому является кодовым словом, степень которого меньше степени g(D). Это противоречит тому, что g(D) является по определению нормированным кодовым словом, имеющим в данном коде минимальную степень.
Доказательство 2. Если g0 = 0, то g(D) = D[gmD"l~l + ... + gj. Однако D не может быть делителем многочлена DN — 1 ни при каком N и, следовательно, g(D) также не может быть делителем. Поэтому g(D) не может быть порождающим многочленом.
6.22. После того, как первый информационный символ выйдет из регистра в линию, в крайнем левом разряде регистра будет храниться —h^cN_l. В следующий момент времени во втором слева разряде будет храниться —h0xN_l —
D*+ l=g(D)[D5 + D4+?> +1].
1 0 0 1 1 0 1 1 1
//=0 11
1 0 1
0 1 0
0 0 1
644
— М/у—2 и аналогично после того, как х N_L поступит в линию, в крайнем
L— 1
правом разряде будет храниться а
г=0
L- 1
—L—1 ' 2j hiXN~i—1-
I = О
Анализируя каждый последующий символ тем же способом, получаем
L— 1
i = О
Это означает, что коэффициенты x(D) h(D) при N — 1 > п > L равны нулю и, следовательно, x(D) является кодовым словом.
6.23. (а + б) Из свойства цикличности следует, что любая циклическая серия последовательных L символов кодового слова может рассматриваться как последовательность информационных символов, а остальные N — L символов могут быть вычислены по ним. Поэтому любая серия не более чем N — L последовательных стираний может быть исправлена, если рассматривать циклически
1...——\ Регистр в, ; L разрядов ~j------------)¦
<
Регистр %
последующие L символов как информационные. Если произошло N — L + а, а > 0, последовательных стираний, то первые N — L из них могут рассматриваться как проверочные символы и могут быть выбраны так, чтобы образовать кодовое слово при каждом выборе остальных стираний. Поэтому с принятой последовательностью согласуется 2“ кодовых слов и декодирование неоднозначно.
(в) Представим себе, что во время работы изображенное на рисунке устройство производит N — L сдвигов. Принятое слово, у которого стирания заменены нулями, поступает в декодер в течение первых N единиц времени, когда ключ А замкнут. Ключ В замкнут в течение первых L единиц времени и регистр а наполняется символами принятой информационной последовательности. В течение последующих N — L единиц времени, когда принимаются проверочные символы, в регистре а не происходит сдвигов, затем производится считывание L информационных символов. Регистр b сдвигается в каждый момент из общего числа N L единиц времени. Нетрудно убедиться, что когда первый стертый символ выходит из регистра а, в регистре b будет содержаться стертая последовательность. [Аналитически это означает, что после N + i сдвигов в регистре b будет храниться Rg(D) [qN—l+i г(Д)]> Где = означает стертую часть
x(D). Если стерт отрезок от (N — i— 1)-го символа до (N—/ — 1)-го симво-
ла, i > j > i — (N-
L)t то ' Rg{D){DN-L+l гф)) = Rg{D) [D^1 z(D)], что совпадает с последовательностью стираний.] В этот момент ключ С находится в правом положении и производится исправление. Определение этого момента должно производиться счетчиком, который начинает подсчет в момент, когда первое стирание поступает в декодер и замыкает ключ при счете N.
645
Единственная нерассмотренная здесь проблема состоит в том, что делать с последовательными блоками принятых символов. Наиболее простой путь ее решения состоит в замене каждого разряда регистра b на два разряда, проведении каждую единицу времени двух сдвигов, и изменении фаз при изменении блоков.
6.24. (а) Задача совпадает с задачей 6.4; объем алфавита не влияет на рассуждения.
(б) I. Линейный (N,L)-код над GF(q) имеет qN~L различных синдромных последовательностей. Число различных расположений i ошибочных символов
равно и каждый ошибочный символ может принимать любое из q — 1 отличных от нуля значений элементов в GF(q). Поэтому число различных конфигураций г ошибок равно (q — I)1". Так как каждой исправимой конфигурации
ошибок соответствует один синдром, то для исправления всех конфигураций е ошибок должно выполняться
