У. Питерсон - Коды, исправляющие ошибки (1267328), страница 90
Текст из файла (страница 90)
Вес первого столбца этой матрицы равен (и,— 1) (д — 1). Если соответствующие проверочные суммы ортогональны, то равенство (13.5) выполняется. Если бы эти два выражения были не ортогональны, то в матрице Н имелся бы прямоугольник, образованный единицами, и все эти четыре единицы находились бы в некоторой матрице Рь Но это невозможно, так как такой же прямоугольник (повернутый на 90') тогда должен был бы быть и в проверочной матрице первоначального кода, что противоречит его самоортогональности. Для таких низкоскоростных кодов из равенства (13.5) и следствия 13.1 вытекает нижняя граница для гп Пример. Множества целых чисел, использованных в предыдущем примере, могут также быть применены для построения само- ортогонального (42,14)-кода.
Его основная проверочная матрица имеет вид ГООО 100 ООО ООО !ОО 100 ООО ООО ООО ООО !.100 ООО 100 ООО ООО ООО ООО 100 ООО ООО 000 000 000 110~ ООО ООО ООО 10!Я' (13.8) Пример. Декодер для самоортогонального (42,28)-кода с д = 5, рассмотренного в предыдущем примере, показан на фиг. 13.9.
Нуль появляется на выходе каждого из мажоритарных элементов, когда два или более нулей поступают на его четыре входа. Каждая из строк этой матрицы определяется одним из двух множеств целых чисел, задающих код. Например, легко видеть, что в соответствии с первым множеством О, 8, 9,!2 первый проверочный символ в блоке с номером 0 проверяет информационные символы в блоках с номерами 0,8,9 и 12. Минимальное расстояние кода равно по меньшей мере 9, так как для каждого блока имеется 8 ортогональных проверочных сумм относительно любого информационного символа.
Теорема 13.2 сводит задачу построения кода к построению непересекающихся полных разностных треугольников. Робинсон и Бернстейн !259! привели обширный полученный на ЭВМ список множеств целых чисел, которые определяют самоортогональные коды с различными скоростями.
Следствие 13.3 и равенство (13.7) показывают, что самоортогональные коды значительно длиннее, чем наилучшие при данных скоростях и минимальном расстоянии коды. Но это в некоторой степени компенсируется простотой схемы их декодирования. Для самоортогонального (тпэ, таз)-кода г( — 1 символов синдрома ортогональны относительно каждого из Аэ информационных символов декодируемого блока. Таким образом, в логической схеме, представленной на фиг.
13.7, можно использовать Аз мажоритарных элементов с И вЂ” 1 входами каждый. При использовании самоортогональных кодов размножения ошибок не происходит. Для того чтобы выходная последовательность изменилась, более половины символов ортогональных синдромов должны быть единицами. Таким образом, обратная связь уменьшает вес синдрома и применима теорема 13.!. Робинсон !258) показал, что самоортогональные коды могут быть декодированы методом дефинитного декодирования, хотя при этом и происходит некоторое ухудшение характеристик декодирования.
Инрориаиионмый ргаиппр с й=гд Яоейнгиаи Иснраеяемае оиибон Модигранацая самдродаа Вод на~ „ Фиг. 13.9. Мажоритарннй декодер еамоортогонального (42,23)-кода. Можно построить самоортогональные коды, которые могут исправлять как случайные ошибки, так и пакеты ошибок. Эти «диффузные» коды рассматриваются в гл. 14. 13.5. Ортогонализируемые коды Эти коды более эффективны при исправлении случайных ошибок, чем самоортогональные коды, но к настоящему времени их конструкция еще не достаточно понята. Все известные коды построены с помощью громоздкого метода проб и ошибок, который, по-вндимому, работает только при Ар = 1; Месси 12051 и Люки, Салз и УелДон [1901 составили таблицы двоичных кодов при скоростях ~/т, /е, ~!в и ~/1а. Ортогонализируемые коды в одном важном отношении отличаются от самоортогональных.
Для последних надо строить множество из г! — 1 ортогональных проверочных сумм, соответствующих строкам матрицы Н. С другой стороны, для ортогонализируемых кодов гр — 1 ортогональных проверочных сумм должны соответствовать строкам матрицы Н или их линейным комбинациям. Таким образом, декодер для такого кода при Ае = 1 будет иметь такой же вид, как на фиг. 13.10, а при Ае ) 1 должны быть добавлены мажоритарные элементы.
Заметим, что этот декодер аналогичен указанному на фиг. 13.7, но логическая схема состоит из множества сумматоров, за которыми следует мажоритарный элемент. Испрпппенпь!е сипепппм Фиг. 13.!О, Декодер ортегеиааизируеного евертечного кода при йа= 1. 11 00 11 00 ОО 11 10 00 00 11 10 !О ОО 00 11 10 10 !О 00 ОО 11 (13.9) Четыре проверочные суммы, определяемые первой, четвертой, пятой строками и суммой второй и шестой строк, ортогональны относительно первого символа.
Декодер для этого кода с несколько другим множеством ортогональных проверочных сумм показан на фиг. 13.8. Это множество проверочных сумм выбрано для того, чтобы проиллюстрировать возможность размножения ошибок при использовании ортогонализируемых кодов. Поскольку условия теоремы 13.1 здесь не выпалнены, выход регистра слвнга нелинейной обратной связи, состоящего из синдромного регистра и мажоритарного элемента, может быть периодическим при нулевом входе. Коды, двойственные к описанным в равд. !З.З кодам, исправляющим одиночные ошибки, ортогонализуемы. При любом лг су. ществует равномерный код !2051 с параметрами п,=2 ', йе — — 1, г1=1т+1)2 .
(13.10) Для этих низкоскоростных кодов матрица Ь представляется в виде Ь=~Р„',О Рт,ь ... Раб где матрицы 0 и 1 имеют размерность (2 — 1)Х(2 ' — !) а матрица ~Рм~,Рг з ... РД размерности (2 — 1) Хт представляется как (1)а ' 2)2 00... 011 00... 101 00... 111 ),Рт-~ Рм-з ° ° ° Ро1= г г т г 1!3.! !) 11 ... 101 1 1 ... 1 1 1 (2 ' — 1)а ! Можно показать, что относительно информационного символа блока с номером 0 можно построить д — 1 ортогональных проверочных сумм !205!.
1тример. Проверочная матрица ортогонализируемого 112, б)- кода с с! = 5 имеет вид Пример. Пусть т = 3. Двойственным к (12,9)-коду из примера, приведенного в равд. 13.3. является равномерный (12,3)-код. Бго проверочная матрица 11 101 ! 001 !000 !! 0000 !О1 !ооо !оа! оооо !000 и !аао оооо !о! 1000 1000 ! 00! Строки 1,2,3,4,5 !т! б, 7 Я 9 и 8 ортогопальны относительно информационного символа в блоке О. Таким образом, и' (т+ 1)2 -з = = 8.
Теорема 13.1 не применима к равномерным кодам. Однако Салливан [292[,показал, что для таких кодов проблема размножения ошибок не столь уже серьезна. В работе [118) описано несколько ортогонализируемых кодов, найденных при помощи ЭВМ. Кроме этих кодов и кодов Месси [2051 построенных вручную методом проб и ошибок, мало что сделано в решении задачи построения хороших ортогонализируемых сверточных кодов. 13,6. Коды, построенные с помощью ЭВМ Перебрав всевозможные субпорождающие многочлены, Бассган [38) нашел все сверточные коды со скоростью '/з при и ( 32 и скоростью '/з при и 21, которые имеют максимальное значение минимального расстояния. Лин и Лайн [185) расширили список хороших сверточных кодов, используя следующую идею.
Пусть известен сверточный (тпм тйз)-код с максимальным значением минимального расстояния. Построим ((и+ 1)по, [пг+ 1)йа)-код, присоединяя набор длины ла к каждому субпорождающему вектору так, чтобы минимизировать количество кодовых слов минимального веса. Более длинные коды образуются таким же способом по индукции. Хотя и не гарантировано, что коды, полученные этим методом, имеют максимальное значение минимального расстояния, это имеет место довольно часто, а в известных случаях, когда это не так, разница мала. Хорошие коды со скоростями 1/з и 1/а прн п(42 были построены с помощью этого метода. Таблицы этих кодов вместе с кодами со скоростями /г = '/м '/в '/ь '/а '/м '/ь з/а и з/з приведены в работе [185). Форин [92] составил таблицы кодов с /г = '/з и и ~ Об.
Костелло (581 описал несколько дРУ~их алгоРитмов нахождения сверточных кодов умеренной длины с хорошими кодовыми расстояниями. 13.7. Алгоритм декодирования Витерби Если число кодовых слов в сверточном коде достаточно мало, то можно использовать следующий метод декодирования. Вначале последовательно порождаются все д» кодовых слов, каждое из которых сравнивается с принятым словом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
