Галкин В.А., Григорьев Ю.А. - Телекоммуникации и сети (1053870), страница 18

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 18)

Представим строку v. через сумму других строки запишем v. на место какой-либо строки, входящей слагаемым в данную сум­му. Таким образом, если верно наше предположение, то в подматрице А могутсуществовать две одинаковые строки, что, в свою очередь, влечет за собойравенство соответствующих проверочных разрядов, так как должно вьшолняться равенство (2.36).

В результате получаем, что наличие в подматрице А ин­формационных разрядов линейно зависимых строк влечет за собой наличие впорождающей матрице линейно-зависимых строк. Но так как, по определению,в порождающей матрице все строки независимы, то и в подматрице А этойматрицы не может существовать линейно зависимых строк.Линейно независимые вектор-строки матрицы А порождают Л-мерное ли­нейное пространство, содержащее 2^ элементов, которое может быть вьфажено любой системой к линейно независимых векторов, принадлежащих этомупространству, в том числе и единичной матрицей размера кхк:1ОО1(2.55)ОО812. Основы телекоммуникацииКанонический вид порождающей матрицы удобен тем, что существует про­стая связь между элементами порождающей и проверочной матриц: для опре­деления проверочной матрицы [п, к] -кода, порождаемого матрицей вида (2.53),нужно транспонировать подматрицу проверочных разрядов матрицы G^ ^ и при­писать справа к полученной матрице единичную матрицу размерности г х г.Таким образом, матрице (2.53) соответствует проверочная матрица (2.45).Коды Хэмминга.

К систематическим корректирующим [п, А:]-кодамотносятся коды Хэмминга с кодовым расстоянием rf = 3. Из табл. 2.2 видно,что число разрешенных кодовых комбинаций для кодов с ^ = 3 равно Л^< 2"{ 1 ++ пук Для кодов Хэмминга выбрано предельное значение разрешенных кодовыхкомбинаций 7V= 2"(1 + пУ\ а число информационных разрядов к определяетсякак:к = log[2Xl + пУ] = дг - log (w + 1).(2.56)Данное уравнение имеет целочисленные решения А:=0,1,4,11,26,..., которыеи определяют соответствующие коды Хэмминга [3,1 ]-код, [7,4]-код, [15,11 ]-коди т.

д.Рассмотрим, в качестве примера, построение [7,4]-кода. Для этого восполь­зуемся каноническим представлением (2.53) порождающей матрицы G^ ^. Под­матрица проверочных разрядов этой матрицы должна состоять из различныхненулевых строк. Определим зависимость числа проверочных г и информаци­онных к разрядов для кодов Хэмминга:2* = 2^1 + пУ или 241 + «)= 2*2^учитьшая, что п = к + г, получим к -^ г + I =2'' или к = Т- г - 1.Общее число ненулевых строк, которые можно составить из г-разряднойкодовой комбинации равно 2^^ - 1, из них г следует вьпесть для образованияединичной матрицы г х г, которую следует добавить к транспонированнойматрице проверочных разрядов при определении проверочной матрицыHnk.

Тогда остается (2'^-г-1)г-разрядныхстрок с числом единиц не менее двух. ЭтоДля единичнойчислоравно числу информационныхподматрицы проверочнойразрядов А. Распределение ненулевыхматрицыстрок для [7,4]-кода представлено на рис.2.14. В этом случае порождающая мат­Для проверочныхразрядов в порождающейрица будет содержать единичную под­матрицематрицу размерностью А: х /: и подмат­Рис. 2.14. Распределение ненулевых рицу проверочных разрядов размерностьюстрок [7,4]-кода82к X г\2.2.

Методы защиты от ошибок и сжатия данных10о0GiA-00 0 0 11 0 0 1 0о 1 о 1 10 01 1 111(^1(2.57)Проверочная матрица строится путем транспонирования подматрицы про­верочных разрядов порождающей матрицы и добавления единичной подмат­рицы г у. г:10 1 1 1 1 О 01^7,4-1 о 1 1 о 1 0|1 1 010 0 1(2.58)Из этой проверочной матрицы легко получить систему проверок, связьюающую проверочные и информационные разряды кода по формуле (2.36).

Хэмминг предложил размещать проверочные разряды в позициях кодовой комби­нации, кратных целой степени двойки, это позволяет по виду синдрома сразуопределять ошибочный разряд кода. Рассмотрим алгоритмы кодирования идекодирования на примере [7,4]-кода Хэмминга.Алгоритм кодирования. Все номера позиций кода нумеруют в двоичнойсистеме счисления, начиная с единицы р-разрядным двоичным числом:р = flog п\, где Г 1 - ближайшее большее целое, п - число разрядов кода...С....С,.сспПроверочныеразряды размещают в позициях кода, кратных целой степенидвойки 2^ 2', ...их д.: с =6 ,7 = 2', /=0,1,..., (г-1), где г-число проверочныхразрядов. Значение с проверочного разряда определяется как сумма по mod2тех разрядов кода, в номере которых двоичный разряд с /-м весом равен еди­нице.пПример. Пусть информационный кодовый вектор v = 1101.

В коде Хэмминга этот вектор,начиная с младшего разряда, буцет занимать позиции Cj, Cj, с^ и с^, а позиции Cj, с^, с^ отводятсяпод проверочные разряды кода. Пронумеруем все позиции кода в двоичной системе счисления:^m^iio^ioif^ioJ^oiiKiJf^ooJ ^ выделим позиции для размещения проверочных разрядов:^111Cm11^1010^^1000'^011^010^0011101Определим значения проверочных разрядов кода суммированием по mod2 тех разрядовкода, в номере которых двоичный разряд с I-M весом равен единице:/ = 0-^2°->с^,=с<,„Фс,„,ес,„;•'^по® «^п,;(2.59)» = 2 - > 2 ^ - » с , ^ = с.„.832.

Основы телекоммуникацииТаким образом, получен кодовый вектор v '= 1100110, который передают по каналу, подвер­женному влиянию помех. Пусть вектор ошибки равен е = 0000100, тогда принятая из дискретно­го канала кодовая комбинация будет иметь внц:v"= 1100010 = v' е е.(2.60)Алгоритм декодирования. Вычислим значение синдрома ошибки:^оо. = РЛ_,...А,-Л11-(2-61)Значение /-го разряда синдрома определяется как сумма по mod2 тех раз­рядов принятого кода, включая проверочные, в номере которых вес двоичногоразряда совпадает с весом разряда синдрома:^=^00, Ф^оп Ф '^.о.® '^п,;^ 2 = ^ 0 , 0 * ^ 0 , . ® '^ПО® ^ПР(2.62)^3=^,00® ^ , 0 , ® ^ПО® ^ПГawepa v" =1100010:Л, = Cj Ф Cj Ф С5Ф с,= 0 Ф 0 Ф 0 Ф Ь= 1;Н^= с^ Ф Cj Ф с^Ф Cj= 1 Ф 0 Ф 1 Ф 1= 1;(2.63)А = с^ Ф с, Ф с^Ф с= 0 Ф 0 Ф 1 Ф 1= 0.34567Синдром ошибки Е^^ = II ^3^2^111 "^ 1|011|1 определяет в двоичной системеномер разряда, в котором обнаружена однократная ошибка.

Для исправленияошибки необходимо инвертировать третий разряд - с^ кодового вектора:v" = 1100110, откуда, выделяя информационные разряды, получаем исходныйкодовый вектор v = 1101.Циклические коды. Линейный [«, Л]-код называют циклическим, если врезультате любого циклического сдвига кодового вектора получают другой ко­довый вектор, т. е. если v = а^а^ а^.., а^^- кодовый вектор, то v' = а^^а^а^,,а^2 ~ другой кодовый вектор.Представим кодовый вектор v = а^а^ а^,„ а^^ полиномом степени {п - \)или меньшей степени: v (дс) = ci^^x^^ +...+ а^^ + а^х -^ а^- кодовый полином.Рассмотрим двоичные циклические коды, в которых основание х выбираютравным двум, а операция суммирования ведется по mod2.

Для кодированияциклическим кодом используются так назьгоаемые порождающие полиномы(« - Л)-степени. Пусть необходимо закодировать сообщение, представленное ввиде кодового полинома т{х) = 'w^.,^"* + ... + т^х + /w^, где к - количествоинформационных разрядов. Умножив т{х) на л:'^*, получим полином степени{п - к) или меньшей степени:х'^''т(х) = т^_^х'*-^ н-... + т^х'^'^^ + т ^ ' ^ ^84(2.64)2.2. Методы защиты от ошибок и сжатия данныхРазделим (2.64) на порождающий полином g{x) степени {п - к):x'^-'mix) = q(x)g(x) + р(х\(2.65)где д(х) - частное, p(jc) - остаток.Так как степень полинома g(x) равна (п - к), то степень остатка должнабыть равна (п- к- 1) или быть меньше:P W = Р.-,-,^"-'-^ + .-.

+ Р2^' + Р,^+ Ро-(2.69)Формулу (2.65) можно представить в ином виде, где левая часть уравнениякратна g(x):р(х) '^x"-'m(x)=q(x)g{xr(2.70)Раскроем (2.70) с учетом (2.64) в виде полинома степени (п - 1):х"~''т(х) + р(х) = т^_^х"~^ + ...+ т^х"~^'^^ + т^"'^ ++ Р„.,.,^''-'-^+...+ Р,^+Ро.^^'^^^в данном виде формула (2.71) соответствует кодовому вектору v == m^_j.../Wj/WQp^_^ J... р2Р,Р, • Отсюда следует, что циклический код информа­ционного сообщения т(х) состоит из неизменного сообщения т^ ^...т^т^ и при­соединенного к нему остатка p^_^_j... PjP^.Важным свойством циклического [л, Л]-кода является то, что порождаю­щий полином g{x) является делителем для полинома л:" + 1: л:^ + 1 = g{x)h{x),где h{x) - проверочный полином. Зная h{x) можно однозначно определитьпорождающий полином g{x).

Например, для циклического кода [7,4]g(л:)=l+л:+x^ Л(л:)=^ ^^=х'' + х' + х-\- 1.XH-JC + 1Существует теорема, которая доказывает, что если g{x) - полином степени[я, к] является делителем для полинома дс^ + 1, то g{x) порождает циклический[я, А:]-код. Действительно, любой делитель х" + 1 степени {п - к) может по­рождать циклический код.

Для больших п выражение л:" + 1 может иметь мно­го делителей степени {п - к). Некоторые из них порождают эффективные коды,а некоторые - нет.Обычно в качестве порождающего полинома выбирают примитивный по­лином степени г = {п-к) из числа неприводимых полиномов той же степени.Полином/7(л:) степени г с коэффициерггами, принимающими значение из множе­ства {0,1}, является неприводимым^ tcjmp{x) не делится ни на один полиномс двоичными положительными коэффициентами степени, меньшей чем г (де­лятся только на единицу и на самого себя).Неприводимый полином р{х) степени г называют примитивным тогда итолько тогда, когда л^ + 1 не делят на/7(л:) для я < 2'^ - 1, т. е.:852.

Характеристики

Список файлов книги