7.1.2. Декодирование с табличным поиском

Декодеры с табличным поиском применяют в тех случаях, когда требуется при очень простой реализации декодера получить выигрыш от кодирования около При этом обычно используют демодулятор с жестким решением. Чтобы размеры таблицы имели разумные пределы, длина кодового ограничения должна быть небольшой. Реализация таких декодеров весьма похожа на ту, которая показана на рис. 7.2 для кода с

7.1.2.1. Реализация. Общая структурная схема сверточного кодера с и декодера с обратной связью, содержащего устройство поиска в таблице, показана на рис. 7.4. В литературе этот метод декодирования называется также просто декодированием с обратной связью [68]. Длина кодового ограничения должна быть сравнительно небольшой Как уже указывалось, для хорошей работы декодера параметр декодирования должен быть выбран большим Этот параметр определяет число символов синдрома, на основе которых решающее устройство вычисляет корректирующий символ. Заметим, что устройство для вычисления синдрома представляет собой регистр, первые ячеек которого вычисляют и имеют такие же связи, как регистр в кодере. Длина регистра сделана равной с тем, чтобы он мог служить для временного хранения принятых информационных символов до их исправления. Регистр синдрома — это другой регистр длиной в котором хранятся символы синдрома, используемые в решающем устройстве. Этот регистр обладает также обратной связью, которая задается порождающим многочленом кода она позволяет устранить влияние всех подлежащих исправлению принятых информационных символов на символы синдрома.

Декодер работает следующим образом. Данные кодируются систематическим кодом с Полученные информационная и проверочная последовательности передаются по цифровому каналу. Принятые последовательности вводятся в устройство вычисления синдрома, вычисляющее Для каждого

Рис. 7.4. Кодер и декодер с обратной связью, содержащий устройство табличного поиска

кодового ребра в устройство поступает по одному символу из последовательностей с помощью которых вычисляется один новый символ последовательности который поступает затем в регистр синдрома. После поступления нового символа в этот регистр последние символов синдрома определяют адрес в таблице решающего устройства. По существу, среди всех комбинаций ошибок, приводящих к данным символам синдрома, решающее устройство выбирает ту, при которой получается наименьшая вероятность ошибки. Если эта комбинация содержит ошибку в символе, который должен покинуть регистр данных, решающее устройство выдает 1, исправляя таким образом эту ошибку. В противном случае решающее устройство выдает 0. Корректирующий символ вновь поступает в регистр синдрома по линии обратной связи, исключая тем самым свое влияние на те символы синдрома, которые будут просматриваться решающим устройством в следующие моменты. До тех пор пока в декодере не возникает ошибок, процесс декодирования будет происходить в точности так, как было описано. Однако ошибка декодирования вызывает неправильный символ обратной связи, что в свою очередь ведет к короткому пакету ошибок (эффект распространения ошибок).

На рассматриваемой структурной схеме не показана синхронизация кода. Как и для других сверточных кодов, нужно обеспечить лишь синхронизацию ребер или вершин. Это значит, что, если последовательности были мультиплексированы перед передачей, их нужно снова разделить. Это можно сделать несколькими способами. Один из простейших состоит в том, чтобы рассмотреть долю исправляемых декодером ошибок (т. е. долю символов 1 на выходе решающего устройства). Если эта доля существенно выше ожидаемой вероятности ошибки в канале, то синхронизация декодера, по-видимому, нарушена и следует позаботиться о ее восстановлении. Блок, подсчитывающий долю ошибок и восстанавливающий синхронизацию, устроен очень просто.

Решающее устройство обычно реализуется на основе постоянной памяти (ПЗУ). Таким образом, каждому синдрому ставится соответствие наиболее вероятная комбинация ошибок на этапе проектирования системы. Для этого обычно используется полный перебор. Проверочная матрица систематического кода с является полубесконечной и может быть записана в виде

Синдром и последовательность ошибок в канале могут быть записаны в виде векторов

Как было показано, зависит только от ошибок и задается формулой

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

Подматрица является единичной матрицей порядка которая умножается на проверочное подмножество в Матричное уравнение

задает систему из линейных уравнений, связывающих символов синдрома с ошибками в канале. Таким образом, для каждого вектора синдрома существует много векторов ошибок в канале удовлетворяющих (7.27). Вероятность первой ошибки декодирования будет минимальной, если для каждого из возможных синдромов найти вектор с наименьшим весом Хемминга, удовлетворяющий (7.27), и использовать найденные векторы в таблице решающего устройства. Для каждого из найденных решений минимального веса значение должно быть использовано в качестве корректирующего символа, выдаваемого решающим устройством. Набор решений для всевозможных обычно находится путем перебора. Заметим, что этот перебор нужно произвести только один раз и найденные решения определяют содержимое таблицы, в которой осуществляется поиск.

Описанный подход реализуется в декодере, в котором достигается минимальное значение но не обязательно минимизируется Построение оптимальной таблицы для минимизации является очень трудной задачей, поскольку в каждом декодере с

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

Заметим, что сложность реализации растет линейно с ростом и экспоненциально с ростом (объем таблицы равен Поэтому в решающем устройстве необходимо использовать умеренные значения Предполагая, что основной вклад в сложность вносит решающее устройство, следует выбирать коды, оптимизирующие характеристики системы при заданном Определим как минимальное расстояние между нулевым путем и всеми путями из нижней половины кодового дерева, усеченными до первых ребер. Ясно, что для оптимизации характеристик следует выбрать генераторы кода, максимизирующие Однако если для данного имеется несколько кодов с одним и тем же то код, для которого при является наименьшим, содержит минимальное число путей веса . В работе [69] для поиска оптимальных кодов с использован именно такой критерий; некоторые коды из этой работы перечислены в приложении табл. Эти коды имеют нечетное кодовое расстояние, которое достигается при наименьшем возможном значении . В таблице приведен только один порождающий многочлен, поскольку коды являются систематическими. Хотя описанный метод декодирования применим и к несистематическим кодам, они не дают никаких реальных выгод. Для каждого из перечисленных в таблице кодов можно найти эквивалентный несистематический код с меньшим значением однако уменьшение не оказывает заметного влияния на сложность [69].

7.1.2.2. Характеристики. Характеристики системы можно проанализировать так, как в подразд. 7.1.1.2; используя полный перебор, можно получить выражение для любого конкретного кода. Несмотря на то что этот подход может дать границу снизу для которая обычно лишь вдвое или втрое отличается от истинного значения, во многих случаях желательно получить более точное значение В этих случаях следует использовать моделирование рассматриваемого кода и решающего устройства на ЭВМ. В интересной для практической реализации области значений вероятность ошибки хорошо аппроксимируется следующим образом:

где К — константа, определяемая в процессе моделирования. Зависимость от для нескольких интересных кодов при когерентной фазовой модуляции показана на рис. 7.5 [68, 70]. Фактический выигрыш от кодирования при сравнительно невелик. Выигрыш от использования кода с составляет

Рис. 7.5. Характеристики декодеров с табличным поиском и с обратной связью

всего в то время как для других кодов он равен примерно Интересно, что коды с меньшей скоростью не приводят к существенному улучшению характеристик. Для каждого из кодов на этом рисунке показано также выражение для вероятности ошибки в виде (7.28), которое может быть использовано для оценки параметров в других каналах с жестким решением. Табличный поиск сравнительно плохо сочетается с применением демодуляторов с мягким решением. При мягких решениях в качестве входов таблицы нужно использовать символы синдрома, а также последовательность вспомогательных символов, указывающих на надежность символов синдрома. Однако такой подход оказывается весьма сложным даже при небольших значениях поскольку объем таблицы экспоненциально растет с ростом числа двоичных символов в адресе. Поэтому декодеры с поиском в таблице применяют лишь в случае жесткого решения.

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

произвести некоторое перемежение символов. К счастью, реализация любого декодера типа декодера Меггитта позволяет легко производить внутреннее перемежение. Для этого достаточно заменить каждую ячейку на рис. 7.4 регистром сдвига с D ячейками. Эта процедура разбивает принятые данные на D независимых кодовых последовательностей, которые переводятся декодером в D независимых декодированных последовательностей. Каждый пакет ошибок в канале, длина которого не превышает D, приводит не более чем к одной ошибке в каждой из D последовательностей. Если длина всех пакетов не превышает D и пакеты возникают независимо, то характеристики этого метода совпадают с характеристиками в канале со случайными ошибками при том же значении

В приведенном обсуждении предполагалось, что, как на рис. 7.4, последовательности и передаются по раздельным каналам, так что пакеты ошибок в этих двух каналах не зависят друг от друга и их длина не превышает D символов. Если последовательности должны быть мультиплексированы (уплотнены) и должны передаваться по одному каналу, то метод нужно слегка видоизменить. А именно, прежде чем производить мультиплексирование последовательностей и следует осуществить задержку одной из них на символов, а после операции, обратной мультиплексированию, эту задержку скомпенсировать. Тогда при появлении пакета его влияние на информационные и проверочные символы будет разделено промежутком, длина которого не меньше кодового ограничения декодера. В остальном декодер работает так, как было описано выше. Рассмотренный метод позволяет обрабатывать пакеты ошибок, длина которых может достигать не вызывая ошибок декодирования. Для введения перемежения в декодеры другого типа (например, декодеры БЧХ. Витерби или последовательные) обычно приходится применять какие-либо дополнительные устройства. Этот подход будет рассматриваться в разд. 8.3.