У. Питерсон - Коды, исправляющие ошибки (1267328), страница 94
Текст из файла (страница 94)
14.2 и !4,4, обычно имеют Ь = пе, и укааанное ограничение не существенно. Кроме того, блоковое перемежение, по-видимому, имеет некоторое преимущество с точки зрения реализации кодов по сравнению с символьным перемежением. По этим причинам в этой главе рассматривается только блоковое перемежение. (См. задачи 14.3 и 14.4.) Перемежение со степенью ! блокового (п,й)-кода, имеющего корректирующую способность для пакетов Ь, приводит к блоковому (пй Ь1)-коду с корректирующей способностью для пакетов Ь1. йвпвмввввпью символы фпг 14.2. Кодер сверточного (З,4)-хода, полученного согласно схеме фиг, 14,1 и перемежепзого со степенью 2. С другой стороны, перемежение сверточного (тпм тйо)-кода с корректирующей способностью для пакетов Ь приводит к (ото(!— — 1)+по,тй(г' — 1)+Ао)-коду с корректирующей способностью для пакетов Ьг.
Это следует из определения длины ограничения. (См. задачи 14.1 и 14.2.) Перемеженне оптимального сверточного кода типа В2, т. е. кода, лежащего на границе, определяемой теоремой 4.18, всегда приводит к коду, также оптимальному в этом смысле. (См. задачу 14.4.) Проверочная и порождающая матрицы перемеженного кода связаны с соответствующими матрицами базисного кода простыми соотногпениями. Пример. Проверочная матрица О! !О 01 1О 1О 01 00 10 1О 01 задает двоичный (8,4)-код с Ь= 2. Перемежение его со степенью 2 приводит к (14, 7)-коду с Ь = 4; его проверочная матрица имеет вид 01 ОО 01 10 00 01 00 10 00 01 10 00 !О 00 01 00 10 00 10 ОО 01 00 00 10 00 1О 00 01 Кодеры для этих двух кодов приведены на фиг.
14.1 и фиг. 14.2. Поскольку перемежение не изменяет скорость кода, то из кодов, описанных в равд. 14.2 и 14.4. можно получить близкие к оптимальным сверточные коды произвольной длины, исправляющие пакеты, практически для любого значения скорости. Если для некоторого кода Ь ~ пм то имеется по меньшей мере два по существу различных способа построении декодера. Идея самого простого метода состоит в последовательном декодировании блоков, как и для кодов, исправляющих случайные ошибки.
Второй метод основан на исправлении всего пакета, как только его начало обнаруживается в блоке с номером О. Обе процедуры можно использовать при декодировании кодов, описанных в равд. 14.2, и они будут рассмотрены в этом разделе. 14.2. Коды Берлекэмпа — Препарата — Месси Двоичные коды, представленные в этом разделе, имеют один проверочный символ на блок [18, 207, 2461. (Коды со скоростью Л ( '!х обсуждаются в разд. !4.4.) Базисный код имеет корректирующую способность Ьз — — и, для пакетов типа В2.
Коды с большими значениями корректирующей способности могут быть построены псремежением. В случае пз-— — 2 и 3 длина кодов, полученных на ЭВМ (см. задачу 14.5), такая же, что и у соответствующих БПМ-кодов, и эти коды даже имеют Ь =- и;, таким образом, они несколько лучше, чем БПМ-коды. Однако эти коды, по-нидимому, не обобщаются на другие скорости. При любом пз существует (2п~з, 2п," — 2п )-код с корректирующей способностью пз для пакетов типа В2. Проверочная матрица такого кода представляется в виде (14.5) н = (в.в,в, ... в~ ,), где матрица В; получается из матрицы Б;, усечением и сдвигом вниз, т. е. 0 0 0 ... 0 1 0 0 ...
0 О 1 О ... 0 0 0 ! ... 0 в,, В.= Ю О 0 О ... 1 0 То что для этого кода Ьт = ле, означает, что единицы произволь- ного ненулевого слова не могут быть заключены в блок О и в один какой-нибудь другой блок. Любой набор длины п, единицы кото- рого находятся в блоках О и 1, может быть представлен в виде Е = Еаб О О ° ° В~О О ° ° О где Е ~ О. Тогда если можно выбрать Ва так, чтобы ЕН не равнялось нулю при произвольном выборе Еа-ьО, Е, н й то для такого кода бх — — ао.
Чтобы это имело место, должно выполняться следующее условие: ЕОЕ 1В В;1г Ф О, 1 ~1 (2% — 1. (14.6) и матрица (ВаВД оказывается невырожденной тогда и только тогда, когда невырождена матрица уь Нижнюю часть матрицы Во первоначально можно выбрать так: О ... О О О О ... А О С В О РЕЕ> О Х!НО (14.7) где пустые места означают нули. Буквы, обозначающие двоичные переменные, должны быть выбраны так, чтобы выполнялось неравенство (14.6). Тогда матрицы у~ могут быть выражены через зти переменные. Если теперь по 1 2па — 1, то правый верхний квадрант матрицы (ВаВД является нулевым и имеет порядок лм Таким образом, выбор верхней части матрицы Ва в виде произвольной не- вырожденной матрицы гарантирует, что равенство (14.6) справедливо при ла(1~ 2пс — 1. Декодирование упрощается, когда этот набор сделан в виде единичной матрицы порядка па, обозначаемой через 1,, При 1 1 пе — 1 неравенство (14.6) выполняется, когда матрицы 1ВаВ~~ являются в совокупности невырожденными.
Производя элементарные операции над строками, можно привести эту матрицу к виду Пример. пс = 4 оо !о О А 01 своо ЕПОА оо о оо л о 0 С В А Р Е (Х)+ С) В о !Оо АО!О в оо'! пооо Двоичные переменные А, В, С, ... можно в алфавитном порядке подобрать так, чтобы все квадратные подматрицы, правые верхние !тлы которых совпадают с правыми верхними углами каждой из матриц Уь были невырожденными. Это возможно потому, что: 1) каждая буква появляется на диагонали минора точно в одной матрице У;; 2) каждый другой элемент подматрицы, находящийся в левом нижнем углу, найден заранее и 3) алгебраическое дополнение этого элемента отлично от нуля в силу предложенной выше конструкции или же поскольку оно является определителем единичной матрицы (см.
[18!). Пример (продолжение). В случае па= 4 выбором значения одной из буквенных переменных обеспечивается невырожденность следующих матриц: ~ (выбираем Л=1). ["1 0 11 с 010 А 0 1 (выбираем В=1), ВО 0 с 001 0 Л 0 (выбираем С=1). СВА Затем выбирается 0 = 1, Е = 1 и Р = 1, с тем чтобы были соот- ветственно невырожденными матрицы 1'з, Уз и т'ь йлмйрмадппннна римарлы 1 Ясно, что значении буквенных переменных не зависят от по. Первые несколько переменных имеют следующие значения: А 1 С В 1 1 РВЕ> 111 Х 7 Н6 1011 О!УМ 7.
К 10011 УТЗ 77 Я Р 100011 (14.8) Заметим, что при таком подборе значений для букв коды Берлекэмпа — Препарата — Месси (БПМ-коды) являются систематическими, но прн этом проверочный символ каждого блока передается раньше его информационных символов. Обычные схемы кодирования и вычисления синдрома должны быть изменены, для того чтобы учесть это различие. Па фнг.
14.3 показан кодер с (и — й) ячейками для (32, 24)-кода БПМ с и, = 4. Для построенных таким образом кодов с йо — — по — 1 достигается граница для Ьз, заданная теоремой 4.17 с неравенством, замененным на равенство. Коды с йо ( ао — ! могут быть построены либо тем же способом 12461, либо с использованием следующей идеи. Если даны (тппоьпз,йо~)- и (тзиоз, тзйоз)-коды с корректирующими способностями для пакетов Ь| и Ьз соответственно, то третий код с асз = птя + пет, йоз = йа~ + Аоь Ьз = Ь! + Ьз и тз = = шах(пзь те) может быть построен просто перемежением блоков по одному для каждого первоначального кода.
Этот искусственный способ позволяет строить коды, для которых ни йм ни по — йо не равны единице. фнг. 14.3. Кодер (32,24)-кода БПМ с и — А ячейками. Проверочный символ передается первым, а аа ним передаются информационные симаолы с номе- рами 1. 2, 3. Базисные БПМ-коды могут декодироваться следующим образом. Предположим, что одиночный пакет имеется в блоке с номерам О.
Поскольку верхняя часть матрицы Во выбрана в виде единичной матрицы, то первые по символов синдрома совпадают с комбинацией ошибок, сложенной с блоком номера О. Для декодирования блока требуется только дополнительная информация о том, находился ли пакет в блоке с номером 0 или же в другом блоке. Если пакет ошибок возник в блоке с номером О, то вторая половина синдрома должна иметь вид з=Е[В [г, (14,9) где через Ео обозначен пакет ошибок, Воо — нижняя часть матрицы Во, а зо — вторая половина синдрома. Другими словами, поскольку первая половина синдрома (з~) равна Ео, то, если во+ з, [Воо[г = О, (14.10) т=-(2по — 1)1+ 1, п=тпо=(2п — 1)по!+ п, й=тйо, Ьо !по Ь = Ь вЂ” ( — 1) = по (! — 1) + 1, д= и — 1 или и — Ьо (см.
ниже). (14.11) Для больших значений т' корректирующая способность этих кодов для пакетов приближается к верхней границе для Ь, определяемой равенством (14.2). Самым очевидным способом декодирования перемеженного БПМ-када являются независимая обработка потоков из 1 символов и декодирование блока за блоком, как и в случае базисного БПМ- када.
Имеется и альтернативная процедура декодирования одиночных пакетов, которая приводит к несколько меньшему защитному пространству, Прием происходит нормальна, пока в блоке с наме- пакет ошибок находится в блоке с номером О, в противном случае в блоке с номером 0 его яет. Соотношение (14,! 0) представляет собой по линейных равенств, составленных из символов синдрома; такие равенства могут быть реализованы с помощью одного сумматора по модулю 2 с несколькими входами. Тогда одного элемента «И» с по входами достаточно для установления гаго, выполняется ли равенство (14.! 0). Перемежение со степенью ! базисного БПМ-кода приводит к коду со следующими параметрами: ром О не возникает ошибок. Тогда эти ошибки принимаются в качестве начала пакета, который занимает первые ! блоков.
Такой пакет может быть исправлен следующим образом. Если все ошибки в 1-и «фазе», 1 «( ! < 1, ограничены блоком с номером О, то, поскольку В»=1„„первые и» символов синдрома этой фазы совпадают с искаженными символами блока с номером О. Таким образом, исправление может просто осушествляться прибавлением первых пз символов синдрома к блоку с номером О для всех ! фаз. Последние л» вЂ” 1 символов синдрома не используются при 2:== ! ~ й Защитное пространство, требуемое для перемеженного БПМ- кода с параметрами, приведенными в (14.11), когда потоки из ! символов декодируются независимо, равно и — 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
