Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
ИСТОРИЧЕСКИЕ ЗАМЕЧАНИЯ И ССЫЛКИ
Питерсону (1961) принадлежит классическая книга по методам алгебраического кодирования, в которой обсуждаются различные вопросы, не освещенные здесь. Берлекэмп (1968) внес большой вклад в теорию алгебраического кодирования к изложил ее на современном уровне. Для всех тех, кто может получить лекции Месси (1967), мы рекомендуем их как превосходное изложение предмета. В книге Возенкрафта и Джекобса (1965) дано введение в последовательное декодирование и связанные с ним вопросы, рассмотренные в § 6.9. Книга Месси (1963) является классическим пособием по пороговому декодированию.
Невозможно перечислить здесь все значительные статьи по методам кодирования. Довольно полная библиография работ в данной области приведена Питерсоном (1961), Питерсоном и Месси (1963) и и Коутцом (1967). В историческом плане следует, однако, отметить следующее. Работа Хэмминга (1950) предопределила большинство работ в‘теории алгебраического кодирования. Слепян (1956) первый изложил коды с проверкой на четность на четкой математической основе. Элайсу (1955) принадлежат результаты § 6.2, а также первое описание сверточных кодов. Прейндж (1957) первый изучил циклические коды. Методы кодирования для кодов Боуза — Чоудхури (1960) и Хоквингема (1959) были впервые развиты Питерсоном (1960) и Дирлером (1960). Последовательное декодирование было изобретено Возенкрафтом (1957), а рассмотренный здесь алгоритм принадлежит Фано (1963). Первые коды, эффективно исправляющие пакеты ошибок, были построены Хейгельбергером (1959) и Файром (1959).
ПРИЛОЖЕНИЕ 6А
Прежде чем приступить к доказательству теоремы 6.9.1, полезно переписать правила алгоритма декодирования так, как представлено на рис. 6А.1. Заметим, что условия, указанные на рис. 6А.1, содержат все условия, представленные на рис. 6.9.4, а также некоторые дополнительные условия. Поэтому, если применяется некоторое правило из описания алгоритма на рис. 6А.1, то оно должно совпадать с правилом, указанным на рис. 6.9.4. Чтобы показать, что некоторое правило применимо к каждой проверке на рис. 6А.1, можно воспользоваться индукцией по последовательным проверкам. Рассмотрим каждое из правил на рис. 6А.1; предположим, что данное правило применимо, и рассмотрим условия, которые возникают при следующей проверке. Например, если применяется правило 1, то для следующих проверок Г;_! > Т и это является новым условием, добавляемым к правилам 1, 2 и 3.
324
Пра Условия в узле Действия, которые следует
вило выполнить
Предыдущее Сравнение и с перво Окончательный порог Движение
движение начальным порогом Т
1 F или L 7’<Гг_1<7’ + Д, Т,>Т Повышается F
2 F или L гг_1>г+д, гг>г Не изменяется F
3 F или L Гг_!>Г, Гг<Г Не изменяется L или В
4 В Гг_1<Г, Ti>T Понижается на Д F
5 В Гг_!>7\ Ti>T Не изменяется L или В
Рис. 6А.1. Множество правил, эквивалентное множеству правил, указанному на рис. 6.9.4.
Доказательство теоремы 6.9.1 (пункт а). Мы хотим показать, что пути порогов и цен, связанных с проверками узла и;, удовлетворяют соотношениям (для 0 < i < / — 1):
Г;<Г; (6А.1)
Ti+1 > Tit (6А.2)
Ti+1>Ti+A=>Ti + A>Ti, (6А.З)
Ti+1> Ti+A^Ti+1> Ti. (6A.4)
Последней проверкой для любого узла и;, предшественника текущего узла ui, должна быть ^-проверка, поскольку и; может быть достигнуто лишь при движении вперед из Uj. Поэтому к щ должно быть применено одно из правил 1, 2 или 4, и в каждом случае должно выполняться (6А.1). Далее заметим, что (6А.4) является прямым следствием (6А.З); соотношение (6А.4) является соединением неравенств в (6А.З). Теперь докажем (6А.2) и (6А. 3),используя индукцию по последовательности узлов, просмотренных декодером. Для первой проверки в начальном узле справедливость (6А.2) и (6А.З) тривиальна, поскольку множество i пусто при 1=0. Теперь предположим, что (6А.2) и (6А.З) выполняются при проверках в произвольном узле и; с последовательностью порогов Т0, _, Ti. Рас-
сматривая сначала движение вперед, затем вбок и затем назад из и/, непосредственными, но утомительными рассуждениями показывается, что соотношения (6А.2) и (6А.З) всегда выполняются в следующем проверяемом узле.
Движение вперед. После движения из иг вперед в узел иг+i пороги Т0,..., Ti не изменяются, но к этой последовательности добавляется новый порог Ti+1. Так как движение в u;+i было движением вперед, к /+1 применимы правила 1, 2 или 3 и окончательный порог Ti+i больше или равен первоначальному порогу Ti, что доказывает (6А.2) для щ+\. Если Ti+1 > Ti + Д, то порог был повышен и должно применяться правило 1. Так как первоначальный порог равен Ti и предшествующая цена равна Г;, то крайне левое условие в правиле 1 принимает вид Г; < Ti + Д, что устанавливает справедливость (6А.З).
