Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Другой метод блокового кодирования для каналов с пакетами ошибок основан на использовании кодов Рида-Соломона (1961). Используемые символы принадлежат полю GF (2т) при некотором т, длина блока равна N = 2т — 1. Для произвольно выбранного минимального расстояния кода, заданного нечетным числом d, число информационных символов равно L = N — d + 1 и любая конфигурация (d — 1)/2 = (N — L)/2 ошибок может быть исправлена. Если представить каждую букву кодового слова т двоичными символами, то получим двоичный код с Lm информационными символами.и длиной блока Nm. Любая шумовая последовательность, которая искажает не более чем (N — L)/2 из этих последовательностей длины т, исправляется; поэтому корректирующая пакеты способность этого кода равна т l(N —L)l2—li+1, при этом код исправляет большое число
316
конфигураций из более коротких пакетов. Отсюда видно, что, увеличивая т при фиксированном LIN, мы подходим сколь угодно близко к теоретическому пределу корректирующей пакеты способности, определяемому теоремой 6.10.1.
Сверточные коды
В этом параграфе рассматриваются некоторые частные методы исправления пакетов ошибок при использовании сверточных кодов. Все эти методы могут быть различным образом модифицированы и обобщены. Однако в настоящее время разработка сверточных кодов для исправления пакетов ошибок еще не вышла из той стадии, когда лучше всего обучить этому искусству на примере. Первый из обсуждаемых методов был независимо развит Ивадари (1967) и Месси*). Он применим
5)
Рис. 6.10.6. Сверточный кодер для R=3U (бит) (а); |3 означает регистр сдвига на |3 разрядов. Сверточный кодер для произвольного R=(\—l)/v (б).
к сверточным кодам со скоростями передачи (в двоичных единицах) вида (v — l)/v, где v — произвольное положительное целое число. Данный метод позволяет для любого положительного целого числа Р достичь исправляющей пакеты способности |3v при защитном интервале |3v (2v — 1) + V2 va (v — 1) — 1. В пределе при больших р отношение длины защитного интервала к корректирующей пакеты способности стремится к 2 V-— 1, что соответствует верхней границе отношения длины защитного интервала к корректирующей пакеты способности, определяемой теоремой 6.10.1.
Блок-схема кодера для метода декодирования Ивадари — Месси изображена на рис. 6.10.6, вначале для частного случая v = 4 (R = = 3/4 бит), а затем — в общем случае. На рис. 6.10.7 представлен декодер для v = 4, из приведенных ниже объяснений станет довольно очевидно, как модифицировать его применительно к произволь-
*> Неопубликованная заметка, июль 1967 г.
317
ному v. В случае v — 4 кодирование производится согласно следующему правилу: при любом п,
/ = 1,2,3,
-- U(„31 2Р_ 2 ® «л - зр- 2 © «л- 4Р- 2 © «л- 50- 3 ©
© W,V—Г>(5—3 J -' ^л —7Р —5- (6.10.26)
Рис. 6.10.7. Декодер для исправления пакетов (метод Ивадари — Месси); /?=3/4.
Символы синдрома Sn определяются через принятые по каналу символы с помощью соотношения
sn = У{п’ Ф Уп- 21? - 2 ф у л- зр - 2 Ф Уп± 4Р - 2 ф
Ф Уп2- 5р-3 © Уп1-6Р-3 Ф Уп1— 7р —5. (6. 10.27)
Из (6.10.26) непосредственно следует, что значения принятых символов в (6.10.27) можно заменить шумовыми символами. Также, если шумовая последовательность содержит лишь пакеты не больше чем из v(3 символов при защитном интервале fVv (2v —1) + 1/2,v2 (v —1) —1, то, как нетрудно убедиться, каждый синдром Sn может содержать не более одного неисправленного шумового символа. Действительно, защитный интервал был выбран так, что в случае, когда z^7p_s является последней ошибкой какого-либо пакета, zi4) не может быть первой ошибкой последующего пакета.
318
Чтобы понять работу декодера, полезно рассмотреть прохождение через декодер пакета из v|3 ошибок. Такой пакет порождает четыре последовательных пакета из единиц в регистре синдрома. Первый из этих пакетов порождается ошибками в четвертом потоке поступающих символов, второй — ошибками в третьем потоке символов, следующий — ошибками во втором потоке и последний — ошибками в первом потоке. Так как длина первого пакета единиц в синдроме не превышает |3, то этот пакет не может быть заблокирован каким-либо из элементов «и», расположенным в нижней части рис. 6.10.7; поэтому пакет исправляется. Последовательность синдрома должна содержать не менее (|3 + 2) нулей между первым и вторым пакетом из единиц; следовательно, эти пакеты не могут перекрыться в регистре синдрома.
Рис. 6.10.8. Кодер для диффузного порогового декодирования.
Появление каждой ошибки в третьем потоке принятых символов увеличивает на 2 число единиц в синдроме и эти единицы отстоят друг от друга на |3 символов, что приводит к исправлению в соответствующий момент символов в третьем потоке. Сумматоры по модулю 2 в нижней части рисунка не позволяют проводить какие-либо исправления в первом и во втором потоках в течение этого времени. Каждое исправление также приводит к изменению соответствующего символа синдрома, так что после исправления последней ошибки в третьем потоке принятых символов регистр синдрома будет целиком заполнен нулями, за исключением, быть может, двух самых левых разрядов. Исправление второго, а затем первого потока принятых символов производится аналогично.
