С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (1127136), страница 12
Текст из файла (страница 12)
е. впне естъ пр.яма.я суммаподпространств С и C_i;•произвольвый вектор из вп может не разлагатьc_l -/:-ся, или разлагаться неоднозначно , в сумму вектора из с и вектора изc_l.128 IIIпоток: Глава3.Коды, исправляrощие ошибкиОпределение 3.4. Пусть { ho,hiЕ вп,i==О,... ,т -1.... , h m- l } - базисcj_'Тогда матрица•••h~-lназывается npoвepolll'НOU .матрицеu кода С.Я сно, что• \l v• HG•Е С:=Hv =О - нулевой т- мерный вектор;О - нулевая(m х k) - матрица;про верочная мат р ица определе на с точностыо доэквивалентных преобразований строк.Например , если л инейный код С задан исходной порождающей матрицейи построена матрицаGGnxk=то проверочной матрицей Н кода С будетHmxn=Im][PmxkДействительно, в этом случае~Hv = HGu=[Pm xkIm]ХIk0Г mxk== (Р + P)u== Ou=О.=(III поток) Коды, исправляrощие ошибки3.3.129Таким образом , линейный код для сообщений длиныkимеет длинуn == k + ти задаётсялибо порождающей матрицей Н размералибо проверочной матрицейnxk ,размер а тхп .GЭти матрицы определены с точностью до эквивалентных преобразований столбцов и строк соответственно ,что соответствует выбору различных базисов в пространствах с иc j_' однакофиксирование позиций информационных бит при систематическом кодировании••задаетпорождающуюипроверочнуiоматрицуодно-значно .Увеличение т ведёт к увеличению кодового расстоянияd(как конкретно- трудный вопрос) и , следовательно, к увеличени1о количества ошибок , которыем ожет исправить код .Пример3.5(кодирования блоковым линейным кодом) .Пусть дан линейный(6, 3)-код С задан порожда1-ощейматрицейоG6 x3о111 о1 о о1 1 11 1 оо 1 1•Требуется:1)с использованием данного кода осуществить(а) несистематическое и(б) систематическое кодирование векторовU1== [0 1 1] Т ИU2== [1 0 1] Т;130 III2)поток: Глава3.Коды, исправляrощие ошибкипостроить проверочнуiо матрицу Н кода;3) определить кодовое расстояние d данного кода.1 (а) .Несистематическоекодированиенаходимнепосредственно (только 3-й бит сообrцениявv••п ереидет1-й бит кодового слова) :о[ v~ v~ ] == G х [ и1 и2]о111 о1 о о1 1 11 1 оо 1 1о1 11 оо 111 о1 1хоо•1 1о 11 (б) .
Для систематического кодирования с помоrцью эквивалентных преобразований столбцов выделимв матрицеGединичнуi{) подматрицу размера3х 3(над стрелкой указано проводимое преобразование надстолбцами) :оо111 о1 о о1 1 11 1 оо 1 1(1)+ (2) 1----t (1)оо11о11оо_,._,G.о1 1о 1 о1 1 1В последней матрице в строках3, 5и1стоит единичн ая подматрица - это приведёт к тому, что1, 2и3-й биты исходного сообrцения последовательно перейдут в3, 5и1- йбиты кодового слова .3.3.(IIIпоток) Коды, исправлятощие ошибки131Н айдём систематическое кодирование и 1 , и 2 :~[ vf v~]2.Gx [ и1 и2]оо11о11ооохо1 1о 1 о1 1 111 о1 11 11 оо 1о 11 ооНаходим проверочнуiо матрицу•оН , формируя~матрицу Рз хз из строкG,отличных от строк с еди-ничной подматрицей:1Рзхзо1О1 1 .1 1 1Для построения проверочной матрицы Н нужно•последовательно разместить столбцы Р в3, 5и1- м её столбцах соответственно,•остальные2, 4и 6-й столбцы Н должны образовывать еди ничну ю подмат рицу.В итоге получим проверочную матрицуНз х 61 1 1 о о о1 О О 1 1 О .1 о 1 о 1 1Б азис С суть столбцы матрицыстроки матрицы н:cl_ -G (или G), а базис132 IIIпоток: ГлаваоG==о3.111 о1 о о1 1 1 '1 1 оо 1 1Убедитесь, что'"'-"G==Коды, исправляrощие ошибкиоо11о11оонто1 1 'о 1 о1 1 1HG == HG ==О1 1 11 о о1 о 1о 1 оо 1 1о о 1-нулевая(3х•3)-матрица .Проверим , что в результате как систематического ,так и несистематического кодирований были действиvтель но наидены кодовые слова:88НХ [ vnvnVV1 2 1 2J3.1 1 1 о о о1 о о 1 1 о1 о 1 о 1 1Найдем кодовое расстояниедируем все 23== 8d.хоооооооооооо•Для этого закосообщений и найдем минимальныйиенулевой хэммингов вес кодового слова:С1 1 1 11 о 1 оо 1 о 1о о о 11 1 1 оо 1 о о== [v1 .
. . vв] == Gх [и1 . .. ив]==3.4.(IIIпоток) Коды, исправлятощие ошибкиоо11о11ооо1 1о 1 о1 1 1и1 ,...,ив-всеоохоооvв-всео8оо8овозможных кодовых слов.Оказалось3.4d=о1 1 1 1о 1 1 о о 1 11 о 1 о 1 о 1возможных сообщений,v 1, . . . ,133о3о1 о 1 о 1о 1 1 о 1 оо о о 1 1 1 11 1 о о 1 1 оо 1 1 о о 1 11 1 о 1 о о 111о•Декодирование линейных кодовМетоды декодирования линейных кодов основанынапредположенииоминимальномчислеп ро изошедших ошибок .Тривиальный метод .воv,П усть передано кодовое слоа приня то словоw = v+ е.Хотя в этом равенстве известно толькоw,ноvЕ Си , по предположениiо , вес вектор а ошибок е минимален .
Поэтому перебир ая все кодовые слова можно вы+числять векторы ошибок ei = wv i , i = 1, 2k и выбрав ek такой, что k = arg m~n ei , восстановить елово...........v = w+ ek.~134 IIIпоток: Глава3.Коды, исправляrощие ошибкиЯ сно , что такой метод тр ебует хранения таблицывсех кодовых слов размера n х 2k и реализации алгоритма нахождения вектора ошибки минимал ьного веса.Известны более эффективные методы декодирования линейных кодов , основанные на использовании по2нятия синдрома .Синдром. Декодирование линейных кодовОпределение3.5 .Сиrндро.мо.м слова w Е{0, 1} n,принятого при передаче сообщения, з акодированного линейным (n, k)-кодом и , возможно , содержащего ошибки ,назовём вектор s ~ Hw Е {0, l}m, где Н- проверочная матрица, т~n- k.С войства синдрома :• s ~О{=}3w -кодовое слово ;• s ~ Hw ~ H(v + e) ~~ + НеНе.=0Отсюда ясно, что в ектор ошибок е удовлетворяет несднородной недоопределенной СЛАУНе~s'а кодовые слова являются решениями соответствующейоднор одной системыHv2~О'Синдром - совокупность явлений, вызванных отклонением от нормы.3 Точнее,s = О означает отсутствие ошибок определённого типа, а не ихотсутствие вообще; это замечаыие относится и к декодированию всех рассматриваемых далее кодов.3.4.(IIIпоток) Коды, исправляrощие ошибки135(или, иными словами - ядром линейного преобразования Н: {0, 1}n --+ {0, 1 }m).Таким образом, вектор е может быть представленкак частное решение е неоднородной системыщее решениеGuсоответствующейе==е+( *) и ободнородной -Gu.и среди всех возможных векторов е необходимо выбрать имеющий минимальный вес.Схема декодирования:ws = Нwн e=sе = е+ Си ll ell--нnin v = wДекодирование по синдрому.тый вектореw,и+еП оскольку и принясоответствующий ему вектор ошибокимеют одинаковые синдромы , можно попытаться восстановить неизвестный вектор е , используя тот факт,что он является решением системы( *) .Для этого нужно составить словаръ синдромов-таблицу, строки которой соответствуют всем возможн ым синдромамs 1,..
. ,s 2rn,а каждая строка содержитнаиболее вероятный вектор ошибок, данному синдромусоответствующий . Этот вектор должен иметь наименьший вес среди возможных решений системыданногоs( *) дляи его называiот лидером класса векторовошибок, имеющих обт.ций синдром s. Если таких векторов минимального веса несколько, то в качестве лидераможет быть выбран любой из них.Таким образом, данный метод потребует храненияпроверочной матрицы размера т х п, словаря синдромов размера2m х п,но не требует нахождения векторов136 IIIпоток : Глава3.Коды, исправляrощие ошибкиошибок минимального веса (они уже найдены на этапепроектирования декодируrощего устройства) .Однако в любом случае алгоритм декодирования••остается••экспоненциально трудоемким и по памяти,ипо числу операций.Пример3.6 (декодирования линейного кода).
Рассмотрим линейный (6, 3) -код из Примера 3.5.1. Закодируем сообщения и == и 1 == [О 1 1]т .Систематическое кодирование для него было ужеполучено: v == [1 1 о о 1 о]т .Пусть при передаче происходит ошибка во 2-м бите ,т.е . принят вектор w == [1 о о о 1 о]т .Н айдём синдром принятого словаw:1Hw1 1 1 о о о1 о о 1 1 о1 о 1 о 1 1охоо11оs.ооЗаранее, при проектировании устройства декодирования, должны быть найдены лидеры классов векторовошибок для всех возможных синдр омов .Для полученного синдрома этот класс составляютстолбцы матрицы всех кодовых слов С (уже полученной в п .
3 Примера 3.5) , сложенные , например , с вектором w . в этом случае для синдрома s == [1 о о] т былполу ч е н класс3.4.(IIIпоток) Коды, исправлятощие ошибки1о1о1ооооо1 1оооо1 1о11 1о1 о 1 о1 1 о 1 оо 1 1 1 1137о1 1о1 1оооо1.Н аименьший вес в этой матрице имеет 4-й столбец, и ,таким образом, лидером интересующего н ас класса является вектор е =[О 1 О О О О]т. Он то и помещаетсяв словарь си ндро мов.Складывая найденный по словарю синдромов данный лидер с принятым словом, получаемv=w +е= [1 0 0 0 1 О] Т + [0 1 0 0 0 О]Т ==[1 1 о о 1 о]тv,и переданное кодовое слово восстановлено верно .Пусть передаётся сообщение и = u 2 = [1 О 1] т;оно кодируется словом v = [1 О 1 1 О о]т.
Пусть такжеошибка опять возникла во втором разряде.Вычи сляемсиндромпринятогословаw = [1 1 1 1 о о]т :Hw1 1 1 о о о1 о о 1 1 о1 о 1 о 1 1х1111о1оs,оот. е . синдро м остаётся прежни м. Ему соответствует тотже лидер е =[О 1 О О О О]т и кодовое слово такжевер но восстанавливается.138 III поток: Глава 3. Коды, исправляrощие ошибкиДекодирование кода Хэмминга.Хэмминга декодированиеможноВ случае кодасущественно упростить.Особенностью проверочной матрицы H mx( 2rn_ 1) кода Хэмминга является то, что её столбцы представляютсобой двоичные коды ч и сел отв Примере3.31 до 2m- 1.Н апример,получ ена матрицаНзх71 1 о 1 1 о о1 о 1 1 о 1 оо 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}
