У. Питерсон - Коды, исправляющие ошибки (1267328), страница 19
Текст из файла (страница 19)
9, являются кодами этого типа. Этот раздел посвящен выводу выражения для числа кодовых слов заданного веса в блоковом максимально разнесенном коде. Если г! = и — й+ 1, то по следствию 3.! любые н — й столбцов проверочной матрицы кода линейно независимы. Обозначим через )у(1, 1м ..., 1») совокупность кодовых векторов, у которых й-я, , 1»-я компоненты равны нулю, и пусть ~1у(1ь 1ь „., 1») ~— число кодовых векторов, содержащихся в совокупности Ы(!ь г», ...
1»). Если й = й, то в )т'(1ь 1»ч ..., 1») содержится только нулевой вектор, т. е. 1)у(6 1м "., 1»)1=1, й-»й Если й ( й — 1, то из следствиЯ 3.1 вытекает, что Ранг матРицы Н(1ь 1, ..., 1»), которая получается из матрицы Н вычеркиванием столбцов с номерами 1ь 1м " . 1», равен и — й.
Следовательно, размерность нулевого пространства матрицы Н((ь 1»» ..., 1») рав- на й — Ь. Таким образом, ~ Ф(1,, (м ..., 1»)1=4»-», й(й Если А; — число кодовых векторов веса 1, то по определению Ат Равно числУ кодовых вектоРов с а — 1 нУлевыми компонентами. Обозначим через 0, общее количество векторов, содержащихся во всех множествах Л'(1ь 1м ..., 1,), у которых з или более компонент нулевые. Тогда Ц = Х ! й(1ь 6.
° ° ., 1))=С'Ч, (3.39) ~<~ < .. ° <~ <» если й =в з; при й <,. з (1, = С„'. (3.40) В сумме У, векторы весов, меньших чем и — з, учитываются несколько раз. Точнее, О, =Ад, + СЗ.~.~А„,-!+ Са.~»А„-в-»+ ° .. + С„"'Ам (3.41) Равенства (3.39) и (3.4!) могут быть использованы для последовательного вычисления чисел Аь Однако явные выражения для чисел А, можно получить исходя из принципа включения и исключения (255). Они имеют вид l А~ = Х ( — 1)» С -~+»О -1+».
(3.42) Подставляя выражения (3.39) и (3.40) в равенство (3.42), получаем 1-Ь-»)-~ (-1)" С"„,+»С„"-'+"д' " '"-"+ »=Ъ ! =С~ Г~ м м и-1-м-и Используя тождество / — м-и — 1 — (-ц" с,"= ~ (-ц" с," а-о а 1-М-М для преобразования выражения (3.42), получаем, что при п — й+1(] =и )-1 — м-и А,=с~ Е ( — ц"с,"(4' ' '" "' — 1). а-о Пример.
Существует максимально разнесенный (8, 4) -код, символы которого принадлежат полю из восьми элементов. Итак, пусть д = 8 и д = 5. Для этого кода в соответствии с формулами (3 44) А,= 588, А,=1736, А = 1379. А0=1~ А1 = Аз = Аз = А4 = О, Аз= 392, Заметим, что К А,=д'. р-в Замгчання Взаимосвязь между кодами с проверками на четность и группамн или векторными пространствами была впервые замечена Кияасу [!76]. Ббльшая часть содержания равд. 3.! — 3.3 данной книги, так же как и некоторые из задач, основаны на содержании фундаментальных статей Слепяна [277, 279].
Ранее Гелей [114] и Хэмминг [!38] рассматривали систематические коды. Описание кода как нулевого пространства матрицы использовалось рядом авторов, а теорема 3.! и следствие из нее были, по-видимому, независимо установлены Саксом [263], Дворком и Хеллером [65], а ранее Боувом в связи с планированием статистических экспериментов. Теорема 3.!1 была впервые сформулирована в качестве предположения Слепяном [279] и доказана Муром в несколько более слабой формулировке. Остальная часть равд. 3.5, включая теорему 3.!1 в ее настоящем виде, основана на идеях и доказательстве Прейнджа, слегка измененных, поскольку в своих оригинальных ПРи ! (1 п — й, РазУмеетсн, А; = О, а Аз — — 1.
Таким обРазом, для любого максимально разнесенного кода распределение весов может быть вычислено достаточно просто. работах Прейидж вместо расстояния Хам минга использовал расстояние Ли [! 80), равд. 3.6 основан на материале статей Макдональда [191, 192), х тя эквивалентные соотношения между весами кодовых слов и „одулярными представлениями были получены Слепяном [277), использовавшим теорию характеров группы, и Боувом и Кеблером [28) использовавшими геометрические соображения. (См.
также аботы [87, 214).) Равд. 3.7 взят из работы Фонтейна и Питерсона 88), (См. также работу Слепяна [279).) Синглетон [276) первый изучал максимально разделенные коды. Результаты равд. 3.9 были независимо получены примерно в одно и то же время в работах [1О, 91, 167). Хотя описание линейных древовидных кодов, приведенное в равд. 3,3, ограничено случаем сверточных кодов, приведенные результаты почти без изменений распространяются на более общие линейные древовидные коды. Этот материал заимствован в большей части из работ [67, 330, 334), но при изложении его в этой книге специально подчеркиваются близкие структурные связи меж. ду сверточными и линейными блоковыми кодами.
Задачи 3.1. Покажите, что линейные коды могут быть определены над кольцом и, таким образом, число символов кода может быть произвольным. 3.2. Покажите, что порождающая (проверочная) матрица линейного кода не всегда может быть приведена к ступенчатой канонической форме, если символы кода не являются элементами поля. 3.3. Для двоичного группового кода, порождающая матрица которого равна Е!~~ 1 найдите: а) порождающую матрицу б в приведенпо-ступенчатой форме для эквивалентного кода; б) проверочную матрицу Н для кода из а); в) кодовое слово, которое имеет 110 в качестве информационных символов.
Покажите, что оно принадлежит пространству строк ~атриды 6 и нулевому пространству матрицы Н; г) стандартное расположение для этого кода. Выберите образующий минимального веса для каждого смежного класса и найКите а~ — число образующих веса 1для 1=0,1,2, ..., 6 (ответ: аз = 1, м = 6, пч =1); д) вектор модуляриого представления (ответ: он содержит шесть единиц и один нуль); е) весовой вектор (ответ: один вес равен О, три веса равны 4, четыре веса равны 3). 3.4. Пусть Н вЂ” проверочная матрица линейного кода.
Покажите, что смежный класс, синдром которого равен ч, содержит вектор веса гв тогда и только тогда, когда некоторая линейная комбинация св столбцов матрицы Н равна ч. (Ср. с теоремой 3.1.) 3.5. Покажите, что если все векторы линейного (и, А)-кода записаны как строки матрицы, то каждый элемент поля в каждом столбце появляется д»-' раз.
Предполагается, что в матрице нет столбца, состоящего только из нулей. (Указание: покажите, что совокупность всех кодовых слов, содержащих О на фиксированном месте, образует подпространство, и рассмотрите смежные классы.) 3.6. Используя результат, сформулированный в задаче 3.5, покажите, что сумма весов всех кодовых слов (и. й)-кода равна л(д — 1)д»-'. Предполагается, что матрица не содержит столбца, состоящего целиком из нулей. 3.7.
Покажите, что в двоичном групповом блоковом коде либо все кодовые слова имеют четный вес, либо половина слов имеет четный вес и половина — нечетный. (Указание: покажите, что кодовые слова четного веса образуют подгруппу.) 3.8. Покажите, что если двоичный групповой блоковый код имеет нечетный минимальный вес, то прибавление проверочного символа, задающего проверку на четность всех символов кодового слова '), увеличивает минимальный вес на !. 3.9.
Покажите, что если линейный (и, А)-код с минимальным весом ш используется при передаче по стирающему каналу и если произошло ш — 1 или меньше стираний, то существует совокупность линейяо независимых уравнений, которые можно разрешить относительно неизвестных символов. Покажите, что имеется по крайней мере один случай а1 стираний, которые не могут быть исправлены.
3.10. Для двоичного блокового кода, используемого в качестве примера в этой главе, декодируйте полученный в результате пере. дачи вектор ч = (10! 11) с помощью процесса поэтапного декодирования. Проверьте, что полученный вектор и является кодовым вектором и что разность ч — и есть вектор минимального веса в своем смежном классе, который предшествует всем другим векторам минимального веса. 3.11. Предполагается известным, что для блокового (13,5)-кода ссс — — 1, 'а~ —— - 13, ах = 78 н ав — — 152. Покажите, что ав ( 2 и все другие а, = О для 1) 5. (Указание: воспользуйтесь теоремой 3.!!.) ') То есть равного сумме всех этих символов. — Прим. род. 3.12.
Найдите модулярное представление для двоичного кода весовым вектором % = (3,4,3,4,3,4,3). Постройте порождаюсщую матрицу этого кода. Предполагается, что в качестве матрицы М выбирается матрица, используемая в примере разд. 3.6. 3.13. Найдите А-перестановки, соответствующие элементарным матрицам размерности 3 Х 3 над полем из двух элементов.
3,14. Постройте матрицы 6 и Н для сверточного (8,4)-кода, для которого Ро= Р~ = Рз =!, Ра = О. Покажите, что для этого кода д = 4. Можно ли построить (6, 3)-код с г( = 4? Задачи 3.15 — 3.19 относятся к систематическим двоичным сверточным кодам. ЗЛЗ. Постройте матрицы 6 и Н для сверточного (12,9)-кода, для которого Рх=[110[, Р, =[10Ц и Ро=[!!Ц. Покажите, что т г т г! = Э. 3.16. Покажите, что не существует сверточного кода с п — й = 3 и д = 3, обладающего более высокой скоростью, чем (!2,9)-код из предыдущей задачи. 3.17. Используемый в примерах этой главы (4,2)-код и (!2,9)- код, введенный выше, являются оптимальными сверточными кодами, исправляющими одну ошибку, с и — й = 2 и и — й = 3 соответственно. Постройте следующий код из этого семейства; (32,28)-код с д = Э.
(Указание: исследуйте вид матрицы Н для этих кодов и примените теорему 3.1 и следствие 3.2 нз этой теоремы.) ЗЛ8 (Вайнер-Эш). Для любого целого т существует двоичный сверточный [т2 -', гп(2 -' — 1)1- код с Ы = Э. Докажите это конструктивно, т. е. укажите вид матрицы Н (или 6) этого кода. Сначала решите задачу 3.!7. ЭЛ9. Лвойсгванный сверточный код определяется как код, порождающая матрица которого получается в результате перестановки Ого н н — 1-го столбцов, 1 а ! ~в, проверочной матрицы первоначального кода (отражения) и затем подходящей перегруппировки строк.
Покажите, что двойственным по отношению к (!2,9)-коду нз задачи 3.!5 является (!2,3)-код, у которого Ра = [11Ц, Р~ = [!ОЦ н Рх = [О! Ц. Покажите„что для этого кода Н = 8. 3.20. Совокупность кодовых слов в некотором узле сверточного древовидного кода образует группу при условии, что учтен результат предыдущего декодирования. Покажите, что если эта информация не используется, то совокупность кодовых слов образует смежный класс по этой группе. 3.21. Пусть (24,!2)-код, а также его нулевое пространство состоят из одного вектора веса О, одного вектора веса 24, а все ~стальные векторы обладают весами, равными 8, 12 или 16. Найдите распределение весов для каждого нз этих кодов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
