?
Построение множества плотных информационных совокупностей для кодов Гилберта и их расширений
Введение. При передаче информации по каналам с группирующимися ошибками традиционным подходом является декорреляция канала и использование кодов, исправляющих независимые ошибки. Процедура декорреляции понижает достижимые скорости надежной передачи, поэтому актуальной является задача использования специальных кодов для каналов с памятью и построения эффективных вычислительных методов декодирования для исправления группирующихся ошибок. Для класса случайных кодов известен подход с использованием информационных совокупностей ограниченного диаметра при исправлении пакетов ошибок. Размер множества информационных совокупностей растет линейно с увеличением длины кода, а построение множества описывается вероятностной процедурой. В работе рассматривается построение множества информационных совокупностей для специального класса кодов, исправляющих пакеты ошибок, называемого кодами Гилберта. Метод. Рассмотрены множества кодовых позиций наименьшего возможного диаметра. На основе вычисления рангов подматриц проверочной матрицы кода Гилберта оценена вероятность того, что набор позиций является информационной совокупностью. Для заданного расположения информационной совокупности проанализированы позиции исправляемых пакетов. На основании проведенного анализа предложена методика построения множества плотных информационных совокупностей для кодов Гилберта с целью исправления всех пакетов ошибок в пределах корректирующей способности кода. Используя особенности задания параметров кодов Гилберта, проведена оценка размера полученного множества плотных информационных совокупностей. Основные результаты. При простом размере блока проверочной матрицы квазициклического кода показано, что для кодов Гилберта на любой позиции находится плотная информационная совокупность. Установлено, что в случае расширенных кодов Гилберта совокупности минимального диаметра существуют только на последней позиции каждого блока. Предложена процедура построения множества плотных информационных совокупностей минимального диаметра для кодов Гилберта и их расширений. Проведено сравнение размера множества информационных совокупностей и вероятность его получения для кодов Гилберта и случайных кодов. Установлено, что количество информационных совокупностей, полученных по предложенной процедуре, не растет с увеличением длины кода. Обсуждение. Полученные в работе результаты, показывают возможность разработки вычислительно эффективных декодеров на основе информационных совокупностей при исправлении однократных пакетов ошибок. В отличие от случайных линейных кодов, для которых методы построения информационных совокупностей, в том числе плотных, носят вероятностный характер, для кодов Гилберта определена процедура гарантированного построения множества информационных совокупностей минимального диаметра. Квазициклическая структура кодов Гилберта позволяет строить множества плотных информационных совокупностей меньшей размерности, чем для случайных кодов. Полученные результаты позволяют гарантировать исправление пакетов ошибок в пределах корректирующей способности кодов Гилберта и их расширений с малой вычислительной сложностью. Использование вычислительно эффективных процедур кодирования и декодирования пакетов ошибок позволит повысить надежность доставки сообщений в каналах с памятью.