Главная страница  Дискретный канал связи 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [ 24 ] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189]

3.7. коды рида -маллера 79

Каждая строка матрицы Gj имеет вес 2"-. Таким образом, любая строка матрицы G имеет четный вес, а сумма двух двоичных векторов четного веса также имеет четный вес (см. задачу 3.11). Следовательно, все линейные комбинации строк матрицы G имеют четный вес, а это означает, что все кодовые слова имеют четный вес. Матрица G,. содержит строки весом 2"-, и, следовательно, минимальный вес кода не превосходит 2"-.

Мы должны доказать, что строки G линейно независимы, и найти минимальный вес кода. Мы докажем, что код имеет минимальный вес 2"- и строки в матрице G линейно независимы. Для этого мы построим алгоритм декодирования - алгоритм Рида, который позволяет исправлять -i- •2" - 1 ошибок и восстанавливать k информационных символов. Отсюда следует, что минимальное расстояние будет не меньше 2"" - 1, но оно должно быть четным и поэтому будет не меньше 2"".

Алгоритм Рида был разработан специально для кодов Рида- Маллера. Можно, конечно, использовать процедуру синдромного декодирования, описанную в § 3.3, но в данном случае осуществить ее довольно сложно. Алгоритм Рида отличается от большинства алгоритмов декодирования тем, что позволяет восстановить информационные символы прямо из принятого слова и при этом не дает точного значения самой ошибки. В этом алгоритме не используются также промежуточные переменные, например синдром.

Предположим, что у нас имеется декодер для кода Рида- Маллера {г-1)-го порядка, исправляющего -1-. 2" -- 1 ошибок. Мы построим декодер для кода Рида-Маллера г-то порядка, исправляющего -•2"-- ij ошибку, сведя этот случай

к предыдущему. Поскольку мы уже знаем, что код Рида-Маллера нулевого порядка может быть декодирован с помощью мажоритарного метода, мы по индукции получим метод декодирования для кодов высших порядков.

Удобно разбить информационный вектор на г -(- 1 сегмент, положив i = [Jo, Ii, If I. где сегмент Ij содержит (7) информационных битов. Каждый сегмент будет умножаться на один блок матрицы G. Кодирование можно представить поблочным умножением вектора на матрицу:



Предположим, что информационная последовательность разбита на сегменты следующим образом: каждому сегменту соответствует один из г блоков порождающей матрицы, который при кодировании умножается на этот сегмент. Если мы сможем восстановить информационные биты в г-м сегменте, то затем сможем вычислить их вклад в принятое слово и вычесть его из принятого слова. Тогда задача сведется к декодированию кода Рида-Маллера {г- 1)-го порядка. Процедура декодирования представляет собой последовательность мажоритарных декодирований и начинается с нахождения мажоритарным методом информационных символов в сегменте с номером г.

Принятое слово запишем в виде

v = IIo, li,

Gr„

+ e.

Алгоритм декодирования сначала по вектору v восстанавливает I,., затем вычисляется разность

Go G,

G, i

которая является искаженным кодовым словом кода Рида-Маллера (г - 1)-го порядка.

Прежде всего рассмотрим декодирование информационного бита tft i, который умножается на последнюю строку матрицы G. Декодируем этот бит, вычисляя 2"~ проверочных сумм по 2 бит из 2"* бит принятого слова, так что каждый принятый бит входит лишь в одну сумму. Проверочные суммы строятся таким образом, что символ вносит вклад только в один бит, а все другие информационные символы вносят вклад в четное число битов в каждой проверочной сумме. Таким образом, при отсутствии ошибок все проверочные суммы равны Но, даже если имеется не более -2--2"--1 ошибок, большинство проверочных сумм по-прежнему будет равняться tVi.

Первая проверочная сумма представляет собой сумму по модулю 2 первых 2 бчтов принятого слова, вторая - сумму по модулю 2 вторых 2 битов принятого слова и т. д. Всего получается 2"- проверочных сумм и по предположению имеется -3"" - 1



ЗАДАЧИ 81

ошибок. Таким образом, мажоритарное голосование проверочных сумм дает правильное значение Для построенного ранее

(16, 1])-кода Рида-Маллера эти четыре суммы выглядят следующим образом:

tlO =Vo + Vi -j- V2 + V3,

iiV = + V5-\-Ve-\- V7,

ilO = V12 -t- Vi3 -f- Vi4 + Vis.

Если произошла только одна ошибка, то одна из оценок, даваемых проверочными суммами, будет неверна; мажоритарное решение дает значение гю- Если произошло две ошибки, то ни одно значение проверочных сумм не встречается чаще других и обнаруживается двойная ошибка.

Аналогично может быть продекодирован любой информационный символ, который умножается на одну из строк матрицы G. Это происходит потому, что любая строка матрицы G ничем не выделяется среди остальных. Перестановкой столбцов мы можем добиться того, что любая строка будет выглядеть так же, как последняя строка матрицы G. Следовательно, можно использовать те же самые проверочные суммы, соответственно переставив индексы у символов, входящих в эти суммы. После построения 2"- проверочных сумм каждый бит декодируется "мажоритарным методом.

После того как эти информационные символы найдены, их вклад в кодовое слово вычитается из принятого слова. Это эквивалентно тому, что мы получаем слово кода Рида - Маллера (г - 1)-го порядка. В свою очередь его последний сегмент информационных битов вычисляется с помощью той же самой процедуры.

Этот процесс повторяется до тех пор, пока не будут найдены все информационные биты.

ЗАДАЧИ

3.1. Порождающая матрица кода над GF (2) задается следующим образом:

10 10 11 0 1110 1 0 110 10

а. Найти порождающую и проверочную матрицу эквивалентного систематического кода.

б. Выписать вектор дуального кода.

в. Выписать стандартное расположение для этого кода.

г. Сколько кодовых слов имеет вес О, 6?

д. Найти кодовое слово, соответствующее информационной последовательности 101. Декодировать принятое слово 111001.




[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [ 24 ] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189]

0.0823