1.2.2. Кодер

В книге рассматриваются два типа кодов: блоковые и древовидные. Определяющее различие между кодерами для кодов этих двух типов состоит в наличии или отсутствии памяти. Кодер для блокового кода является устройством без памяти, отображающим последовательности из входных символов в последовательности из выходных символов. Термин «без памяти» указывает, что каждый блок из символов зависит только от соответствующего блока из символов и не зависит от других блоков. Это не означает, что кодер не содержит элементов памяти. Важными параметрами блокового кода являются и На практике значения лежат между 3 и несколькими сотнями, Значения, лежащие вне этих пределов, являются возможными, но часто приводят к некоторым практическим трудностям. Входные и выходные последовательности обычно состоят из двоичных символов, но иногда могут состоять из элементов

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

При другом подходе коды можно разделить на линейные и нелинейные. Линейные коды образуют векторное пространство и обладают следующим важным свойством: два кодовых слова можно сложить, используя подходящее определение суммы, и получить третье кодовое слово. В случае обычных двоичных кодов эта операция является посимвольным сложением двух кодовых слов по модулю 2 (т. е. Как мы увидим позже, это свойство приводит к двум важным следствиям. Первое из них состоит в том, что линейность существенно упрощает процедуры кодирования и декодирования, позволяя выразить каждое кодовое слово в виде «линейной» комбинации небольшого числа выделенных кодовых слов, так называемых базисных векторов. Второе свойство состоит в том, что линейность существенно упрощает задачу вычисления параметров кода, поскольку расстояние между двумя кодовыми словами при этом эквивалентно расстоянию между кодовым словом, состоящим целиком из нулей, и некоторым другим кодовым словом. Таким образом, при вычислении параметров линейного кода достаточно рассмотреть, что происходит при передаче кодового слова, состоящего целиком из нулей. Вычисление параметров упрощается еще и потому, что расстояние Хемминга между данным кодовым словом и нулевым кодовым словом равно числу ненулевых элементов данного кадового слова. Это число часто называют весом Хемминга данного слова, и список, содержащий число кодовых слов каждого веса, можно использовать для вычисления характеристик кода с помощью аддитивной границы (см. подразд. 1.3.2). Такой список называют спектром кода.

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

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

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