Коды, исправляющие ошибки
Содержание | Назад | Вперед | Лабораторные | О курсе

  Содержание



 

1. ПРОБЛЕМА КОДИРОВАНИЯ

  1.1. Симметричный канал. Блоковые коды

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


Рис. 1. Блок-схема общей системы передачи или хранения информации.

Существует два принципиально различных типа кодов, используемых для защиты от искажений в канале с шумом. В кодере, приспособленном для использования блоковых кодов, непрерывная последовательность информационных символов разбивается на отрезки, содержащие по k символов, или блоки. В дальнейшем операции производятся над каждым блоком отдельно в соответствии с выбранным кодом. Каждому информационному блоку сопоставляется набор из n символов, где n > k. Этот набор называемый кодовым словом, передается по каналу связи, искажается шумом, а затем декодируется независимо от других кодовых слов. Иногда величина n называется длиной кода. Отношение R = k/n, которое характеризует избыточность, необходимую для исправления/обнаружения ошибок, называют скоростью кода.

Если сообщение состоит из большого числа символов, то в принципе лучше использовать один блоковый код большой длины, чем последовательность кодовых слов из более короткого кода, так как случайная конфигурация ошибок обычно имеет вид серии ошибок. Следовательно, при одной и той же скорости более длинные кодовые слова менее чувствительны к ошибкам, чем более короткие кодовые слова. Для примера рассмотрим случай, когда 1000 информационных бит передаются с помощью 2000-битового двоичного кода, способного исправить 100 ошибок. Сравним такую возможность с передачей одновременно 100 битов с помощью 200-битового кода, исправляющего 10 ошибок на блок. Вторая схема также может исправлять 100 ошибок при передаче 2000 символов, но лишь тогда, когда они расположены специальным образом - по 10 ошибок в каждом 200-битном блоке, в то время как первая схема может исправить 100 ошибок независимо от того, как они расположены внутри 2000-битового кодового слова. Следовательно, использование длинных кодовых слов более эффективно.

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

Обозначим через q число различных символов, используемых при передаче сообщений по каналу; где q - степень простого числа, хотя в данном пособии особое внимание уделяется числу q = 2. Блоковым кодом называется множество V q-ичных наборов длины n. Эти q-ичные наборы называются кодовыми словами. Между информационными q-ичными наборами длины k, k<n, и кодовыми словами устанавливается взаимно однозначное соответствие, т. е. каждому слову длины k ставится в соответствие единственное кодовое слово, и обратно, каждое кодовое слово соответствует единственному информационному набору.

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

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

Пример. Предположим что четыре возможных сообщения a, b, c и d будут передаваться с помощью двоичного блокового кода длины 5. Тогда должны быть выбраны четыре кодовых слова, например 11000 для a, 00110 для b, 10011 для c и 01101 для d. Кроме того, предположим, что в канале возможны только ошибки типа замещения символов, т. е. при передаче по каналу в кодовом слове некоторые единицы могут замениться нулями, а некоторые нули - единицами. Для исправления ошибок на приемном конце канала должны быть записаны решения, принимаемые декодером для каждого из возможных  двоичных наборов длины 5. Пример таблицы декодирования приведен на рис. 2.

Кодовые слова 11000  00110  10011  01101  


Другие
принимаемые
слова

11001  00111  10010  01100
11010  00100  10001  01111
11100  00010  10111  01001
10000  01110  11011  00101
01000  10110  00011  11101

x 11110  00000  01011  10101
01010  10100  11111  00001

Рис. 2. Таблица декодирования для двоичного кода с q = k = 2 и n = 5.


Таблица декодирования, приведенная на рис. 2, позволяет выполнять декодирование правильно, если в полученном слове имеется не более чем одна ошибка, т. е. не более чем один двоичный символ был искажен при передаче по каналу. Правильно декодируются и некоторые другие комбинации ошибок. Например, если было передано слово 11000, в котором произошли две ошибки, в результате чего получилось слово 11110, то декодирование будет произведено правильно, так как слово 11110 находится в столбце под 11000. Однако, если в результате двух ошибок получилось слово 11011, то оно будет неправильно декодировано в слово 10011, поскольку 11011 на рис. 2 находится в столбце под словом 10011.

Далее мы рассматриваем модель двоичного симметричного канала. Иными словами мы полагаем, что вероятности появления 0 и 1 в каждом кодовом слове равны. При передаче по каналу ошибки в различных символах равно вероятны и не зависят друг от друга.