6.7. Гибридные методы кодирования

Как было указано выше, важнейшей характеристикой алгоритмов последовательного декодирования является вероятность переполнения буфера. Вероятность переполнения буфера можно понизить, если установить для последовательного декодера максимально допустимое число операций, а символы, для определения которых декодер должен выполнить большее число операций, декодировать другим методом, например одним из алгебраических методов, для которых число операций при декодировании всегда ограничено. Возможность уменьшения вероятности переполнения буфера указанным выше образом строго обосновал Фалконер [16], воспользовавшись для этого рассматриваемым ниже гибридным методом кодирования и декодирования.

6.7.1. Системы гибридного кодирования

Предположим, что по А независимым дискретным каналам без памяти каждые секунд передается один символ канала (фиг. 6.14). Будем считать, что на вход каждого из этих каналов символы подаются с выхода относящегося к этому каналу сверточного кодера. Если используемые в этой системе сверточные коды имеют скорость передачи то на вход любого сверточного кодера информационные двоичные символы должны поступать каждые секунд. Наконец, предположим, что через каждые секунд регистры сдвига всех сверточных

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

Фиг. 6.14. Гибридный кодер.

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

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

Фиг. 6.15. Структура кода (фигуры в соответствуют сечениям и 3 на фиг. 6.14). а — входные символы кодера кода Рида — Соломона; б - параллельный блок; в — суперблок.

а) Структура кодов. Структура кодового слова при гибридном кодировании показана на фиг. 6.15. Как видно из фиг. внутренних блоков формируются при кодировании одновременно и передаются по дискретным каналам без памяти. Эти внутренних блоков образуют один суперблок. Как указано на фиг. 6.15, в, -символов, поступающих параллельно на входы последовательных декодеров, образуют параллельный блок. Верхние -символов параллельного блока составляют независимые подблоки, каждый из которых состоит из информационных двоичных символов и известных фиксированных символов. Остальные -символов параллельного блока являются проверочными и формируются алгебраическим кодером по верхним независимым -символам, с которыми алгебраический кодер оперирует как с элементами поля

Параллельные блоки образуют -ичный блоковый код длины содержащий кодовых слов.

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

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

Далее остановимся на выборе блокового кода. При средних и больших длинах блоков наиболее эффективными кодами являются коды Рида — Соломона. Эти коды могут быть построены для любой скорости передачи и любой длины не превышающей объема алфавита символов, и имеют минимальное расстояние Если рассматривать коды над полем или его расширением, то размер алфавита является степенью числа 2 и должен быть не меньше Последнее условие эквивалентно следующему:

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

б) Декодер. Как показано на фиг. 6.16, гибридный декодер состоит из параллельно работающих последовательных декодеров и декодера кода Рида — Соломона. При декодировании каждого суперблока независимых последовательных декодеров Фано осуществляют декодирование соответствующих внутренних блоков. Декодирование различных внутренних блоков, вообще говоря, может продолжаться различное время. Здесь будем предполагать, что после окончания декодирования последовательными декодерами некоторых внутренних блоков декодирование остальных блоков прекращается и все последовательных декодеров начинают декодирование внутренних блоков следующего суперблока. При этом А-символы, декодирование которых не было завершено, воспринимаются далее декодером кода Рида — Соломона как стирания.

Таким образом, после завершения декодирования суперблока последовательными декодерами он переходит в параллельный блок (параллельный блок — это кодовое слово Рида — Соломона, быть может, искаженное в канале), состоящий из -символов, последовательное декодирование которых было завершено, и -символов, которые рассматриваются как

стирания. Этот параллельный блок подается на декодер кода Рида — Соломона. Предположим, что используемый код Рида— Соломона имеет минимальное расстояние и что среди -символов, последовательное декодирование которых было завершено, имеется не более чем неправильно декодированных -символов. Как хорошо известно, если выполняется соотношение между числом ошибок числом стираний и минимальным расстоянием кода то декодер кода Рида — Соломона может декодировать данный блок правильно. Итак, при гибридном кодировании и декодировании число операций при декодировании всегда конечно и приближенно оценивается величиной порядка или

Фиг. 6.16. Гибридный декодер.

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

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