Cтраница 3
В общем случае он образуется следующим образом. В каждый / - и тактовый момент времени на вход кодирующего устройства поступает kQ символов сообщения: сясй... Величина k называется длиной кодового ограничения. Она показывает, на какое максимальное число выходных символов влияет данный информационный символ. Эта величина играет для сверточного кода ту же роль, что и длина блочного кода. [31]
Как правило, параметры устройства чередования, используемого совместно с кодом с коррекцией одиночных ошибок, выбираются таким образом, чтобы число столбцов N превышало ожидаемую длину пакета. Выбираемое число строк зависит от того, какая схема кодирования будет использована. Для блочных кодов М должно быть больше длины кодового блока; для сверточных кодов М должно превышать длину кодового ограничения. Поэтому пакет длиной N может вызвать в блоке кода ( самое большее) одиночную ошибку; аналогично в случае сверточных кодов в пределах одной длины кодового ограничения будет не более одной ошибки. [32]
Экспериментальные исследования показали, что, как правило, после того как декодер совершит ошибку декодирования, он сделает еще ошибки при декодировании последующих примерно пяти символов, а затем вновь будет декодировать правильно. Для рассмотренного частного кода Месси ( 1964) теоретически показал, что поступление в декодер достаточно длинной последовательности неискаженных символов после ошибки декодирования возвращает декодер к правильному декодированию. Это стремление к размножению ошибок характерно для схем декодирования сверточных кодов. Для очень простых кодов и декодеров типа рассмотренных выше это размножение ошибок не слишком серьезно и обычно приводит лишь к коротким пакетам ошибок декодирования. Однако если увеличивать длину кодового ограничения и усложнять схему декодирования, то это размножение ошибок приводит к более серьезным последствиям. Вместе с тем, чем серьезнее становится проблема размножения ошибок, тем легче декодеру распознать наличие ошибки декодирования. Кроме того, в кодер можно периодически подавать известную последовательность нулей, после чего декодер может начинать декодирование сначала. [33]
В этой задаче изменим эти нереальные предположения на новые. Точнее, будет использоваться ансамбль кодов, введенный перед леммой 6.9. J, с конечной длиной кодового ограничения, равной L подблокам. Изменим также алгоритм декодирования следующим образом. При любом / ( / I), как только декодер произведет первую / - проверку узла на глубине / в дереве принятых цен, он окончательно принимает гипотезу о символах источника в ( / - L 1) - м подблоке и полагает Г; - оо. Другими словами, декодер не может менять гипотезы о символах, от которых узел максимального проникновения декодера в дерево удален более, чем на длину кодового ограничения. [34]
Как правило, декодирование по алгоритму Витерби используется в двоичном входном канале с жестким или мягким 3-битовым квантованным выходом. Длина кодового ограничения варьируется от 3 до 9, причем степень кодирования кода редко оказывается меньше 1 / 3, и память путей составляет несколько длин кодового ограничения [12], Памятью путей называется глубина входных битов, которая сохраняется в декодере. После рассмотрения в разделе 7.3.4 декодирования по алгоритму Витерби может возникнуть вопрос об ограничении объема памяти путей. Из этого примера может показаться, что декодирование кодового слова в любом узле может происходить сразу, как только останется один выживший путь в этом узле. Это действительно так; хотя для создания реального декодера таким способом потребуется большое количество постоянных проверок после декодирования кодового слова. На практике вместо всего этого обеспечивается фиксированная задержка, после которой кодовое слово декодируется. Было показано [12, 22], что информации о происхождении состояния с наименьшей метрикой состояния ( с использованием фиксированного объема путей, порядка 4 или 5 длин кодового ограничения) достаточно для получения характеристик декодера, которые для гауссова канала и канала BSC на величину порядка 0 1 дБ меньше характеристик оптимального канала. [35]
В этой главе рассматривается сверточное кодирование. В главе 6 обсуждались основы линейных блочных кодов, которые описываются двумя целыми числами, п и k, и полиномиальным или матричным генератором. Целое число k указывает на число бит данных, которые образуют вход блочного кодера. Особенностью линейного блочного кода является то, что каждый из и-кортежей кодовых слов однозначно определяется Jt-кортежем входного сообщения. Отношение k / n, называемое степенью кодирования кода ( code rate), является мерой добавленной избыточности. Сверточный код описывается тремя целыми числами я, k и К, где отношение kin имеет такое же значение степени кодирования ( информация, приходящаяся на закодированный бит), как и для блочного кода; однако п не определяет длину блока или кодового слова, как это было в блочных кодах. Целое число К является параметром, называемым длиной кодового ограничения ( constraint length); оно указывает число разрядов jt - кортежа в кодирующем регистре сдвига. Важная особенность сверточных кодов, в отличие от блочных, состоит в том, что кодер имеет память - / г-кортежи, получаемые при сверточном кодировании, являются функцией не только одного входного - кортежа, но и предыдущих К - входных k - кортежей. На практике п и k - это небольшие целые числа, а К изменяется с целью контроля мощности и сложности кода. [36]
Это предположение не является необходимым, однако упрощает объяснения. Из состояния 00 можно перейти только в состояние 00 или 10, как показано на рис. 7.12, а. Суммарная метрика этих ветвей обозначена как метрика состояний Гй, Гь, Гс и Td, соответствующих конечным состояниям. В момент времени t3 на рис. 7.12, в опять есть две ветви, выходящие из каждого состояния. Один из путей, входящих в каждое состояние, может быть исключен, а точнее - это путь, имеющий большую суммарную метрику пути. Если бы метрики двух входящих путей имели одинаковое значение, то путь, который будет исключаться, выбирался бы произвольно. Поскольку переход вызывается единичным входным битом, на выходе декодера первым битом будет единица. Здесь легко можно проследить процесс декодирования выживших ветвей, поскольку ветви решетки показаны пунктирными линиями для входных нулей и сплошной линией для входных единиц. Заметим, что первый бит не декодируется, пока вычисление метрики пути не пройдет далее вглубь решетки. Для обычного декодера такая задержка декодирования может оказаться раз в пять больше длины кодового ограничения в битах. [37]