У. Питерсон - Коды, исправляющие ошибки (1267328), страница 12
Текст из файла (страница 12)
2.14. Покажите, что целые числа по модулю 4 образуют коммутативное кольцо, но не поле. (Ср. табл. 2.2 и задачу 2.1.) 3 Линейные коды В этой главе основкое внимание сосредоточено на линейных кодах„образующих некоторый подкласс в классе всех кодов. Почти все известные блоковые и древовидные коды являются кодами этого типа, н поэтому (с одним исключением) только линейные коды рассматриваются в оставшейся части этой книги. Можно построить линейные коды, символы которых являются элементами произвольного множества (задачи 3.! и 3.2). Однако почти все основные результаты в теории кодирования получены в предположении, что символы кода являются элементами конечного поля.
Таким образом, в дальнейшем будет предполагаться, что число символов д является степенью простого числа. Разумеется, двоичные коды с символами О и ! получаются при д 2. 3.1. Метрика Хэмминга и метрика Ли Совокупность всех наборов элементов поля длины и образует векторное пространство. Некоторое множество векторов длины и называется линейным блоковым кодом тогда и только тогда, когда оно является подпространством векторного пространства всех наборов длины и. Аналогично линейный древовидный код (определение см. в разя, 3.3) — это множество полубесконечных последовательностей, которые образуют надпространство в линейном векторном пространстве всех таких наборов. В случае двоичного канала и, более того, в случае любого поля из р элементов, где р— простое число, любая группа векторов является также подпространством (задачи 2.9 и б.8).
Для двоичных линейных кодов общепринято название групповой код. Кроме того, линейные блоковые коды иногда называют групповыми алфавитами. Вгс Хэмминга вектора т, обозначаемый через гв(т), определяется как число ненулевых компонент этого вектора. Так как расстояние Хэмминга между двумя векторами т1 и тг равно числу компонент, которыми они отличаются, то расстояние между т, и т, равно гв(т1 — т,).
Если векторы т1 и тг являются кодовыми словами линейного кода, то разность т, — ч, также должна быть кодовым словом, потому что множество всех кодовых слов есть векторное пространство. Следовательно, расстояние между двумя кодовыми векторами равно весу некоторого третьего кодового вектора, и минимальное расстояние для линейного кода равно мини- „льноду весу его ненулевых векторов. Это свойство очень помоет при анализе возможности исправления ошибок линейными кодами. Пример. При д = 2 и и = 5 совокупность векторов (О О 0 0 0), (! О 0 1 1 ), (О ! 0 1 0), (1 1 0 0 1), (О 0 1 0 1), (1 0 1 1 О), (О 1 1 1 1) и (1 1 1 0 0) образует векторное пространство $~~ и„ следовательно, линейный или двоичный групповой код.
Минимальный вес равен 2, и, следовательно, минимальное расстояние равно 2. Этот код будет использоваться в качестве примера на протяжении всей этой главы. Построение почти всех известных блоковых и сверточных дов основано на понятии расстоянии Хэмминга. Это относится ко всем кодам, за исключением одного, рассматриваемым в этой книге. Понятие расстояния Ли, хотя и не используется столь широко, как расстояние Хэмминга, все же является очень полезным, и для некоторых классов каналов оно является более естественной метрикой, чем расстояние Хэмминга. Вес Ли набора (а„-и" .
аь ае) длины п, где элементы а; выбираются из множества (0,1,..., д — 1), а д — произвольное положительное число, определяется как и-! гас= Я (а, 1, ю-о где ао если 0(а,~ ~—, (а,1= д — а,, если — (а,~~д — 1, Расстоянием Ли между двумя наборами длины и называется вес Ли разности этих наборов. При д = 2 и д = 3 расстояние Ли и расстояние Хэмминга совпадают; при д ) 3 расстояние Ли между двумя наборами длины п больше или равно расстоянию Хэммннга между этими наборами. П ример.
Пусть д= 5 и и=6. Тогда расстояние Ли между двумя наборами длины 6 а=(2 0 0 2 3 4) и Ь=(2 0 4 0 0 0) равно весу набора, составленного из разностей соответствуюших компонент по модул!о 5: а — Ь =(001234) Таким образом, Ь)=О+О+!+2+2+'=5 3,2. Описание линейных блоковых кодов при помощи матриц Любое множество базисных векторов линейного кода г можно рассматривать как строки матрицы О, называемой лорождаюч1ей жатриней кода и'. Пространство строк матрицы О является пикейным кодом Р, и вектор является кодовым вектором тогда и только тогда, когда он является линейной комбинацией строк чатрицы О.
Если размерность векторного пространства Р равна 'ч, то число строк матрицы О (которое равно рангу О, потому что "троки матрицы должны быть линейно независимыми) равно й. Если бы какие-либо две линейные комбинации были равны, то существовало бы соотношение линейной зависимости между строками матрицы О. Таким образом, различныелинейныекомбинацин дают различные кодовые векторы, и так как имеется й коэффидиентов с и возможными значениями для каждого, то простран:тво Г содержит всего дь кодовых векторов. Такой код называется (и, й) -кодом. Во всех случаях, кроме тех, когда и д и й малы, матричное зписание кода более компактно, чем перечисление всех кодовых ° екторов.
Двоичный групповой (50,30)-код описывается матрицей размерности 30 Р',50, но имеет более чем 10з кодовых векторов. Пример. Код Р~ из предыдущего примера являетсн пространством строк любой из следующих матриц: чНг= О. (3.1) Если ч=(аьаь...,а ) и злемент, входящий в йю строку и 1-й столбец матрицы Й, обозначен через 60, то соотношение (3.1) означает, что для каждого 1 (т. е. для каждой строки матрицы Н) ~ пап-— -О. ! (3.2) Существует также другой способ описания кодов при помощи матриц. Снова, если Ь' есть подпространство размерности й, то го нулевое пространство является векторным пространством Ь" размерности п — й. Может быть построена матрица Н ранга и — й, строками которой является базис пространства Р' и про."транство строк которой совпадает с Р". Далее, 1' есть нулевое пространство для У', и вектор т принадлежит г' тогда и только тогда, когда он ортогонален каждой строке матрицы Н, т.
е. когда ким образом„соотношение (3.1) означает, что компоненты века ч должны удовлетворять совокупности и — й независимых уравнений. Конечно, любая линейная комбинация уравнений (3.2) так1ке дает некоторое уравнение, которому должны удовлетворять оненты ч, и это соответствует тому, что вектор ч ортогонален ждому вектору из пространства 1". Эти соотношения называются обобщенными проверками на четность, поскольку в случае двоичного кода они представляют собой проверку на четность определенных наборов символов в кодовом слове.
Это значит, что для каждой строки матрицы Н число единиц вектора ч, которым соответствуют единицы в строке матрицы Н, четно тогда и только тогда, когда ч удовлетворяет уравнению (3.2). Матрица Н называется проверочной матрицей кода У, Соотношения (3.1) справедливы для любого вектора ч из пространства У. В частности, они справедливы для й базисных векторов матрицы 6.
Эти й уравнений можно записать как ННт (3.3) где 0 обозначает нулевую матрицу размерности й Х(п — А). Пример. Нулевое пространство Уз для векторного пространства У, из предыдущего примера содержит четыре вектора: (00000), (11010), (! 0101) и (О! 1! 1).Этичетыревектора образуют векторное пространство.
Первые два ненулевых вектора линейно независимы и образуют базис. Таким образом, У1 является пространством строк матрицы Код У1 представляет собой нулевое пространство этой матрицы. Каждый вектор из Уз задает уравнение, которому должны удовлетворять компоненты любого кодового вектора. Например, вектору (О 1 1 ! 1) соответствует уравнение Оа, + !ах+ 1аз + 1а4+ 1аз О, которое должно удовлетворяться для любого кодового вектора (аьах,ама„аз).
Для двоичных кодов это эквивалентно наличию четного числа единиц среди последних четырех компонент кодового вектора ч или проверке на четность последних четырех компонент. Заметим, что в отличие от векторов над полем действительных чисел ненулевой вектор над конечным полем может быть ортогонален сам себе. Например, вектор (О 1 1 1 1) принадлежит одновременно У, и Ум Легко проверить, что уравнению (З.З) удовлетворяют приведенная выше матрица Н и каждая нз двух порождающих матриц, приведенных в предыдущем примере. Векторное пространство т' и его нулевое пространство Г' являются подпространствамн пространства наборов длины и, и поэтому оба являются линейными кодами. Они называются двойственными кодами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
