Введение в прикладную комбинаторику, Кофман А. (984071), страница 55
Текст из файла (страница 55)
532). Будем предполагать, что символы взяты из конечного множества, обладающего структурой поля (тогда эти 445 Для этого используем (Б2.7), т. е. !!пс!!=!!рс!! !!рс!! откуда имеем 5/! 0 0 5/10 2/!О 4/!О 4/!О 5/!О 2,5/10 2,5/!О 0 5/10 5/!О 0,05 0 0,05 0,04 0,08 0,08 0,15 0,0?5 0,075 0 0,2 0,2 ссс сссс и с р 0,1 0,2 0,3 0,4 символы можно складывать и перемножать). Особенно удобно пользоваться конечными полями характеристики 2, что мы и будем делать. Хэмминг определил расстояние между двумя кодовыми словами как число мест, в которых символы этих слов не совпадают.
Если, например, С =111 о ! о о ! ! о11, С!=1~о ! ! о ! о ! о11, (БЗ.!) хх хх то /1(С!, С!) = 4. (Б3.2) Расстояние Хэмминга тесно связано с вероятностью ошибки при передаче сообщения. Действительно, пусть передано слово Хь которое принято как слово / ! 1 "71Ч!!, И ~ Ы!х, Ф)=Ь. !БЗЗ! Лалалтаяия Тогда Рис. 332.
р(т! )„Р!) ро.// -и. (БЗ 4) в самом деле, при передаче символа по двоичной симметрической линии вероятность ошибки равна р, а у нас л — 6 символов переданы правильно, а 6 символов — неверно. Так как р всегда меньше 0,5, то р(Х!(~р!) увеличивается, когда 6 уменьшается; отсюда получаем правило: при получении на выходе кодового слова !р! следует в качестве кодового слова на / ! 4 / с! входе брать слово с наименьшим расстоянием от ~р! (рис. 533). ! ! ! ~а ~У Можно проверить, что расстоя- 1 ! ! ние Хэмминга удовлетворяет всем 3~ обычным аксиомам расстояния: 1 / ,4(С,, С!) ~0, (БЗ.5) причем равенство имеет место тогда и только тогда, когда ! = /, т р~ азу/и/Уааа/аяаарЗсшйя Ц д (С„С!) = д (С!, С!), (БЗ 6) Рис. 333.
,4(С„С!)+ ((С!, С,) ~ 4(С„С,). (Б3.7) Для расстояния Хэмминга справедливо соотношение т!У( ч1' (с( (Сс С!) )~ 2з + 1). (БЗ.З) Это означает, что при кодировании словами, расположенными одно от другого на расстоянии не меньше 2е+ 1, получаем возможность исправить все простые ошибки (на одном месте), все двойные ошибки (на двух местах), „., все ошибки на е местах. 443 Если ЧМ1(с((Сь Сг) ) 2е), (Б3.9) то имеется возможность исправить все простые ошибки, двойные ошибки, ..., ошибки на е — 1 местах.
Ошибки на е местах можно обнаружить, но исправить, вообще говоря, нельзя. Действительно, если расстояние между кодовыми словами не меньше 2е + 1, то при получении слова С'; его следует интерпретировать по установленному выше правилу как слово С, (рис. 534), так как от любого другого слова С, оно находится на расстоянии, не меньшем е+ 1. Заметим, что исправить можно самое большее е ошибок. Если минимальное расстояние l с б) уул птенце е+у Рис.
534. Рис. 535. между двумя словами в коде равно 2е, то можно найти два слова с расстоянием е от полученного слова С(, следовательно, обнаруженную ошибку исправить нельзя (рис. 535). Точно так же можно было бы показать, что для исправления е ошибок и обнаружения 1 ошибок при: ) е необходимо, чтобы д(С„Сг) ) и +1+ 1. (Б3.10) Верно также и обратное утверждение. Из сказанного выше очевидна необходимость кодирования. Выяснены также условия, которым оно должно удовлетворять. Остается лишь показать, каким способом кодирование можно осуществить. Известные способы кодирования, дающие возможность обнаружения и исправления ошибок '), используют: 1) подпространства векторного пространства размерности и, при этом слова имеют длину л; это — линейные коды; 2) отношение делимости многочленов; это — циклические коды. Предшественником последних является код Бодо. Циклические коды, будучи менее доступными для теоретической трактовки, чем линейные, практически реализуются значительно легче.
1) Исправление ошибок, по определению, — частный случай обнаружения 447 Двоичные линейные коды. Пусть !!е,!!=|!00 ... 1 ... 00!! (Б3.11) — вектор, все компоненты которого равны нулю, кроме 1'-й, равной !. Эти векторы в совокупности линейно независимы и образуют базис линейного пространства Ю„над полем (1 можно считать единицей поля). Их можно записать как строки матрицы порядка и; о о...о о о ! о ... о о !!! !!= (БЗ.12) о о о ... ! о о о о ...
о Пусть вектор !! а1 !! = 1~ а,а,... а„~1, (Б3,13) где а1 — элементы поля, преобразуется матрицей !!1!! в вектор !! о, !! ен д'„, !! а1 !!!!1!!=!~ о, !!! (БЗ,! 4) т. е. (Б3.15) 1Хл 1Хл лХл тогда !! а, !! = !~ о, !1. 1Хл 1Хл (Б3.16) Если взять другие п линейно независимых векторов и записать их как строки матрицы !|М'!1, то при !!а !! !~ М=!~ о !! 1Хл лХл 1Хл (53.17) имеем, вообще говоря, !! а, !! ~ !! о, !1, (Б3.18) 1Хл 1Хл но, как и в предыдущем случае, умножением на матрицу !!.41!! получаются все векторы из о„. Точно так же можно определить матрицу 1~.кт!|, строки которой представляют собой и линейно независимых векторов (ранга т); с помощью этой матрицы можно получить все векторы из подпространства д' размерности т пространства 1о„: 448 !!все т-выборки элементов поля )! ° )!М!!=(! векторы Ю 1Хм шХл 1Хл (Б3.19) Приведение матриц к каноническому виду.
Рассмотрим следующие действия с матрицами: !) перестановка строк; 2) умножение строки на произвольный венулевой элемент поля; 3) прибавление к строке матрицы другой строки, умноженной на элемент поля. С помо|цью этих действий всегда можно привести матрицу !~Я!~ ранга пг к следующему каноническому виду; о о ... о о о ! о ... о о о о ! ... о о (Б3.20) )=1, 2,..., /г.
а ооо...!о:: о о о ... о ! ! 1!У~1= При этом строки матрицы !!У!! (как векторы) определяют то же линейное подпространство д*, что и строки матрицы 1~.Х!~, т. е. (!все т-выборки из элементов поля !! !!У!!=!!векторы из д' ~!. хп ~ки (Б3.2!) Заметим, что матрица !!У~! преобразует т-выборку в и-мерный вектор таким образом, что первые т координат вектора совпа- дают с соответствующими компонентами выборки, а послед- ние й являются их линейными комбинациями: !! ...
т-выборка ...! ... й-выборка~!. (Б3,22) Приходим к кодам, которые называют систематическими; при передаче кодового слова первые и мест называют информационными, а последние й — проверочными, так как эти линейные комбинации позволяют обнаружить или даже исправить ошибки при передаче информационных символов.
Такой код обозначается через (и, т). Если использовать линейные пространства над полем из двух элементов, то с его помощью можно передать 2'" сообщений. Линейный код общего вида состоит из всех векторов некоторого подпространства линейного и-мерного пространства. Двойственный код. Исходя из кода (и, и), можно непосред. ственно образовать двойственный код (и, и — тв) = (и, А).
Действительно, если Ю вЂ” подпространство, порожденное матрицей 449 !!У~!, то его базис можно следующим образом дополнить до ба- зиса всего пространства: Г 00...О0:,: 0 1 О...О 0,.:' 0 0 1 ... 0 О 1 1~У!!- лиг 1=1, 2,..., лг, (Б3.23) 4 0 0 о...10:1 О О 0...0 Г 0 ... 0 0 ~ ... 0 гг = — а и и )( Я (!-л 0 0 ... 1 й последних векторов образуют базис подпространства д'д пространства з „. Для матрицы ~~У~~ (образованной первыми гп строками матрицы (Б3.23)) имеем тогда ))У ~~=~~ ~) 1 ~11~| А ~1~1; (Б3.24) гиХл 1~ У 1! ~~ М ~Г=(~~ ж 1~ ~~ У ~1')'=~~ О ~~.
(Б3.28) лгХл лХЛ ЙХи ихгл гиХЙ Действительно, записывая сомножители с помощью блоков подходящих размеров (т. е. таких, что число строк блока-множимого равно числу столбцов блока-множителя), получаем !)'0 1„~~'0 А ~~ ~~ -Ь--,- =~~1 ~1 ~~ — А!!+~~А!! ~~!и~1=(~ — А~~+~~А!1=((0!!. (Б3,27) Пространство, порожденное векторами матрицы ~~У~~, называют нулевым пространством для матрицы 1~Ж!! и наоборот. Если 'зоз — и-мерный вектор, полученный из и-выборки !!аз с помощью матрицы!!Я, т. е. $ о ~~=)/ а ~! 'з У з, гхл гХлг Х« (Б3.28) 450 для матрицы ~~М~| (образованной последними й строками матрицы (Б3.23)) имеем '0 Я 0'=1 — 1~ А!!'! 'з 1ь 1~ ~|, (Б3.25) ФХл где ~~А'!~ — матрица, транспонированная к матрице 1~А!1, а ~11,!~в единичная матрица порядка г. Выполняется следующее матричное соотношение: то /! е /! !! М !1'=/! а !! !1 У !! !! Я !!л =!! 0 !!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
