Главная > Разное > Теория кодирования и теория информации
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

3.3. Треугольные, кубические и n-мерные коды

При рассмотрении прямоугольных кодов можно быстро прийти к треугольным, в которых каждый символ на диагонали (их исло равно если сторона треугольника равна определяется

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

Рис. 3.3.1.

Треугольные коды

Рис. 3.3.2. Кубический код; показана только одна плоскость с соответствующей ей проверочной позицией

Сразу же после того, как найден некоторый код, который лучше простых прямоугольных кодов, возникает вопрос: «Насколько вообще можно снизить избыточность?». В случае куба нужно проверить каждую плоскость в трехмерном пространстве (рис. 3.3.2). Три пересекающихся проверочных ребра содержат из возможных символов. Таким образом, чистая избыточность равна примерно

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

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

Задачи

3.3.1. Постройте треугольный код с 10 информационными символами.

3.3.2. Подробно исследуйте четырехмерный 2X2X2х2-код.

<< Предыдущий параграф Следующий параграф >>
Оглавление