1.3. Двоичный симметричный канал

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

Фиг. 1.2. Двоичный симметричный канал.

Фиг. 1.3. Расстояние Хэмминга и исправление ошибок.

Для ДСК вероятность того, что при передаче некоторого кодового слова кода длины ошибки возникнут в определенных компонентах из равна Поскольку то чем меньше тем больше эта вероятность. Следовательно, если предположить, что все кодовые слова передаются с равными вероятностями, то наилучшим решением при приеме является такое, при котором переданным считается кодовое слово, отличающееся от принятой последовательности длины в наименьшем числе компонент. Такое правило принятия решений называется декодированием по максимуму правдоподобия. Из вышеизложенного видно, что введенное в предыдущем разделе расстояние Хэмминга является понятием, важным для ДСК. Чтобы можно было исправлять ошибки в и меньшем числе компонент (далее такие ошибки называются ошибками веса и меньше или t-кратными ошибками), необходимо и достаточно, чтобы для любых двух различных кодовых слов множество различных двоичных последовательностей длины отличающихся в или меньшем числе компонент от т.е. и множество различных двоичных последовательностей длины отличающихся в или меньшем числе компонент от т.е. не имели общих элементов (фиг. 1.3). Другими словами, как следует из утверждения 1.6, необходимо и достаточно, чтобы

Таким образом, код исправляет ошибки веса и менее тогда и только тогда, когда минимальное расстояние кода больше или равно . Аналогично можно показать, что код обнаруживает любые ошибки веса и менее (т. е. ошибки в и меньшем числе компонент) тогда и только тогда, когда минимальное расстояние кода больше или равно

Утверждение 1.7. Для того чтобы код исправлял любые ошибки веса и менее и обнаруживал любые ошибки веса от до минимальное расстояние должно быть не меньше чем

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

Таким образом, как видно из вышеизложенного, минимальное расстояние кода является важным параметром, показывающим, насколько хорошим является код в ДСК. Здесь следует заметить, что при обычно удается исправлять также часть ошибок веса и более (см. пример 3.1 в разд. 3.2).

В некоторых случаях удается более или менее точно установить зависимость вероятности правильного декодирования от вероятности ошибки в канале, но полностью определить корректирующую способность кода только через минимальное расстояние кода вообще говоря, нельзя. Однако, поскольку, за исключением ряда случаев, когда значения параметров очень малы, описать более детальные свойства кода почти невозможно, то обычно корректирующую способность кода характеризуют минимальным расстоянием Исходя из вышеизложенного, говорят, что: 1) среди кодов с одинаковыми параметрами (т. е. в классе -кодов) лучшим является код, который имеет большее минимальное расстояние среди кодов с одинаковыми параметрами лучшим является код, который имеет большее число информационных символов среди кодов с одинаковыми параметрами лучшим является код, который имеет меньшую длину а следовательно, и меньшее число избыточных символов Заметим, что здесь при сравнении качества кодов не учитывают сложность кодирования и декодирования. Поэтому иногда говорят более точно: «код имеет лучшие параметры».

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

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

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

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

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