У. Питерсон - Коды, исправляющие ошибки (1267328), страница 88
Текст из файла (страница 88)
+т, и,.йо(1, )). ! ! Заметим, что это выражение совпадает с соответствующим символом векторного произведения (то! ° ° ° тол!пи ... ги„, ... т<„ и, ... т1„, иа,) б. Для систематического кода бг=(1а,рг1, т. е. при 1~(йа, 1 1„если 1=1, ( О, если 1~=1. Власы г 2 Нц да(ко 2) 1 1 9.(2 Ъ) ! ! 1 1 д (1,па) ° ° 1 1 1 1 пц + ,-к о Вт.1,! дв!-2 Т 1 = ! 1 1 1 1 1 1 1 д -((!.2) " д !(2О 2) 1 ! дп-2(! 2) " дч,-Фа,2) 1"'! дц((,2) ! 1 ! 1 ° . Е ! 2 1 1 ! 1 1 1 дв !((,па) .- дяе!О!а,по) ! ! дв!-г(!1па) '*' 9в ед'а па) 1 ! „1 1 1 1 Эяг.
(3.2. Кодер для сверточке~о (тпе, айе)-кода с й=тйе ячейквмк. 1 да(! т) Пример. Систематический сверточный.код, исправляющий одиночные ошибки, имеет следующие параметры: по = 4, Ао = 3 н и = 3. Его основная проверочная матрица записывается как Ь=(1100 1010 111 Ц. оответствующий кодер показан на фиг. 1З.З,а, субпорождающне иногочлены имеют вид ~м())) =1+ и+ П, д (П) =1+ П-', дат(()) -1+ П.
На фиг. 13.3, б показан вариант этого декодера для последовагельного приема. Если ключ 1 открыт, а ключ 2 закрыт, то йа симюлов из (т,— !)-го блока проходят в регистр и непосредственно юступают в канал. Затем ключ 1 закрывается, а ключ 2 открытается, и считываются пе — Ао последних проверочных символов >лона.
В этот момент кодер готов кодировать следующий блок. вхрды 1 ыхады 1 г 3 Завайвроввяний рвак Риг. 1з.з. Деа типа кодера систематического сиерточиого (!2,9)-кода с (г ичсй~аии и в,ч(В) = 1+ О+ Е~а, им(11) =1+ П', аз4(0) = 1+ О. Зтот тип последовательного декодера может быть использован для любого сверточного кода, представленного как в систематической, к и не в систематической форме.
длина кодового ограничения сверточного кода определяется ак величина, в и, раз большая, чем количество блоков между ненулевыми первой и последней (включительно) подматрицами В~ из равенства (3.12). Во многих случаях П, чь О, и длина кодового ограничения совпадает с величиной п — ограничением длины при декодировании. Однако элементарными операциями над строками можно преобразовать матрицу б в матрицу с формой, отличной от ступенчато-канонической, н несколько меньшей длиной кодового ограничения. (См., например, задачу 13.12.) Хотя множество кодовых слов н корректирующая способность кода при этом не изменятся, новый код отличается от первоначального в двух отношениях. Во-первых, код получается несистематическим, а во-вторых, для него можно построить кодер с меньшим количеством запоминающих устройств.
В систематическом сверточном коде нужно найти только и, — й, значений произведений многочленов. Для этого лучше использовать схему умножения, представленную на фиг. 7.3, а не схему фиг. 7.2, в соответствии с которой строится кодер с регистром, содержащим А ячеек. Кодер, схема которого приведена на фнг. 13.4, имеет п — й запоминающих устройств. Здесь через р,(й1) обозначен (й !)-й элемент матрицы Рь 1= О, 1, ..., т — 1, порождающей матрицы из равенства (3.13).
При кодировании блок из Аа символов одновременно поступает в кодер и канал. По мере прохождения этого блока происходит сдвиг содержимого в кодере и параллельно вырабатываются па — й0 проверочных символов, В этот момент кодер готов к кодированию следующего блока. Заметим, что в кодере с регистром сдвига, содержащим п — й ячеек, на самом деле используется лишь (и — й) — (ла — й,) ячеек. За некоторой сложностью схемы, представленной на фиг.
!3.4, скрыта внутренняя простота кодера. Для большинства практически используемых кодов параметры па и Аа малы. Кроме того, для многих кодов с простыми декодерами ббльшая часть элементов р,(й !) равна нулю. Пример, На фиг. 13.5 приведена схема кодера с (п — -А) ячейками для (12, 9)-кода, рассмотренного в предыдущем примере.
Тот факт, что этот кодер действительно вычисляет проверочный символ в соответствии с матрицей Ь из предыдущего примера, можно проверить, сравнив эту матрицу и схему. Проверочный символ второго блока является суммой трех информационных символов этого блока, первого и третьего информационных символов предыдущего (первого) блока и первого и второго информационных символов нулевого блока, 1 1 оо "о 2 Входы Ьит. 13*4. Кодер лля систематического сверточиого (атаа, гака)-кола с л — й ячейками.
веро чнмк молвы В ! Вюды 3 г Лроверооные символы фиг, 13.3. Кодер (12,9)-кода с и — я ячейками. Процесс вычисления синдрома отличается от кодирования только тем, что принятые проверочные символы должны быть вычтены из проверочных символов, вычисленных по принятым символам, Кроме того, поскольку предполагается, что синдром и принятые информационные символы будут использованы в декодере, их следует записать. Таким образом, обычно синдром вычисляется при помощи регистра с А ячейками, в котором записываются информационные символы.
Для того чтобы использовать кодер, изображенный на фиг. 13.2, или кодер, представленный на фиг. 13.3 в качестве генератора синдрома, необходимо только добавить на выходе регистр с 1п — А) ячейками для записи синдрома. На фиг. 13.6 показана схема, с помощью которой вычисляется синдром для приведенного в предыдущем примере (12, 9)-кода. Поскольку систе- Символы ив канала саваром Фиг. 13.6. Схема получения синдрома для (12,9)-кода, реализуемого согласно :хеме, представленной на фиг. 13,3. магический и несистематический коды эквивалентны, синдромы в обоих случаях могут вычисляться одним и тем же способом. Конечно, при этом соответствие между синдромом и комбинацией ошибок будет различным для этих двух кодов, но в любом случае нулевой синдром соответствует на приемном конце кодовому слову, Как и в блоковых кодах, ошибки обнаруживаются при появлении ненулевого синдрома.
Если сверточный (гппо, тра)-код может исправлять некоторое множество ошибочных комбинаций, то можно построить (пт(па — 1), ат(Аа — 1) ) -код с той же корректирующей способностью. Для этого требуется укоротите каждый блок на 1 символов, а это означает, что первые 1 информационных символов в каждом блоке приравниваются нулю и поэтому не передаются. 13.2. Исправление и размножение ошибок Общая схема декодера для свсрточного (тна, ан7ао)-иода представлена на фиг. 13.7.
Когда ключ 1 открыт, а ключ 2 закрыт, Ао информационных символов поступают в информационный регистр. Затем ключ 1 закрывается и открывается ключ 2. Кодер по принятым информационным символам вычисляет проверочные символы, которые для построения синдрома вычитаются из принятых проверочных символов. Логическая схема определяет по синдрому правильность записанного в информационном регистре самого старшего блока из йа информационных символов. Если имеется комбинация ошибок, которая может быть исправлена, то логическая схема исправляет ошибки в этом блоке с номером О, когда блок выходит из декодера. исааавленнне симввлы аеление Фнг.
13.7. Общая схема декодера для саерточного (п, и)-кода. фиг. 18.8. )[екодер деоичиого ортогонализируемого [12, 6)-кода с Ь= [10101000001 Ц. В это время известны ошибки в блоке с номером О. Они влияют на символы синдромов, соответствующих последующим лг — 1 блокам. Для того чтобы декодер смог полностью реализовать свои корректирующие возможности, следует исключить влияние зтих ошибок. Это может быть достигнуто за счет обратной связи, кото.
рая в схеме, изображенной на фиг. 13.7, представлена пунктирной линией. Обратная связь преобразует синдромный регистр прямого действия в (неликейный) регистр сдвига с обратной связью. Это мо-, жет привести к явлению, названному размножением ошибок '). Неисправимые ошибки в канале могут вызвать переход синдромного регистра в такое состояние, что и при отсутствии аддитивных ошибок в канале декодер будет продолжать всегда декодировать неправильно. Причина итого состоит в том, что выход нелинейного регистра сдвига с обратной связью, когда на его вход поступает нулевая последовательность, а начальное состояние в ненулевое, может быть периодическим. Пример.
На фиг. 13.8 показан декодер для двоичного сверточ. ного (12, б)-кода, исправляющего двукратные ошибки, с матрицей И=110 10 10 00 00 111. «) Некоторые авторы используют термины «бесконечное размножение ошибок» или «катастрофическое размножение ошибок». В втой книге не рассматринаетсн случай ограниченного размножении ошибок. (Это пример ортогонализуемого кода; см. равд. 13.5.) Если имеет место трехкратная комбинация ошибок вида 00 01 00 01 01 00 информационный символ нулевого блока то ошибки будут происходить и тогда, когда в канале не будет никаких аддитивных ошибок. В этом случае синдромный регистр перейдет из состояния 0 1 1 0 1 0 в состояние 0 0 1 1 0 1, затем снова в 011010 и т.
д. В одном нз этих состояний информационный символ, выходящий из регистра, иивертируется неправильно; в другом состоянии — правильно. Влияние размножения ошибок может быть исключено, если декодер для этого примера построить иначе. Однако в общем случае, это, по-видимому, сделать нельзя, поэтому возможность размножения ошибок следует учитывать при проектировании систем, в которых сверточные коды используются для контроля ошибок, Для некоторых кодов, обсуждаемых в этой и следующей главах, размножение ошибок невозможно, для других — возможно.
Следующий результат определяет достаточное условие для декодирования ошибок без их размножения. Теорема 13.1. Если в сверточном декодере под влиянием символов !ненулевой) обратной связи вес синдрома всегда уменьшается, то размножения о!набок не происходит. Доказательство. При наличии ошибок появляется ненулевой синдром. Размножения ошибок ие будет, если синдромный регистр очищается при поступлении на его вход нулевой последовательности. Предположим, что все символы синдрома для нулевого блока равны нулю.
Тогда сдвиг синдромного регистра приводит к сдвигу синдрома вправо на пь — А, символов и к заполнению синдрома слева пь — йь нулями, так что его вес уменьшается из-за обратной связи. Таким образом, повторные сдвиги либо приводят к нулевому синдрому, либо к синдрому, у которого блок с номером 0 является ненулевым. В последнем случае дополнительный сдвиг уменьшает вес синдрома независимо от обратной связи. Когда синдром достигнет нулевого состояния, никаких дополнительных ошибок декодирования быть не может. Ч.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
