Галкин В.А., Григорьев Ю.А. - Телекоммуникации и сети (1053870), страница 17
Текст из файла (страница 17)
Общая идея исправления ошибок кратности не более q^ заключаетсяв следующем. Число возможных кодовых комбинаций М помехоустойчивогокода разбивается на Л'^ классов по числу Л^ разрешенных кодовых комбинаций.Разбиение осуществляется таким образом, чтобы в каждый класс входили однаразрешенная кодовая комбинация и ближайшие к ней запрещенные. При декодировании определяется, какому классу принадлежит принятая кодовая комбинация. Если кодовая комбинация принята с ошибкой, т. е.
является запрещенной, то она исправляется на разрешенную кодовую комбинацию, принадлежащуютому же классу.В теории кодирования доказывается, что для обеспечения возможностиисправления ошибок кратности не более q^ кодовое расстояние должно бытьбольше 2q^. Обычно оно выбирается по формуле d = 2q^+ 1.762.2. Методы защиты от ошибок и сжатия данныхАктуальной является задача определения наибольшего числа N разрешенных кодовых комбинаций /7-разрядного двоичного кода с кодовым расстоянием d, В теории кодирования существуют следующие отношения:1d=ld=2d=3d=2q+lN = 2"Л^ = 2"-'Nu2"(l+ny*(" Л\'=1-1N<2"-\\ + j^C„)Матричное представление [n, А:]-кодов. Среди блочных кодов широкоераспространение получили линейные коды.
Линейными w-ичными кодами назьшаются Л-мерные подпространства я-мерного линейного векторного пространства. При этом число п имеет смысл длины кодовой комбинации, число к определяет число информационных разрядов. Линейные коды называют также[я, А:]-кодами.Среди линейных кодов особую роль играют групповые коды, для которых7W = 2 (двоичные коды).
Существуют различные способы задания групповыхкодов. Наиболее распространенными являются матричное описание кодов изадание их с помощью порождающих многочленов.Запишим кодовую комбинацию (кодовый вектор) группового кода длиной пв следующем виде a^a^..Mfi^b^.„b^, Первые к разрядов являются информационными, остальные г = п-к - проверочными. Проверочные символы кодовыхкомбинаций формируются из информационных символов на основе выражения*У=^Л'^^1^2 +(2.36)•^^,Л; у =1,2,..., г.Здесь коэффициенты с j, с^,..., с^ принимают значения из множества {0,1}.Любая кодовая комбинация, состоящая из к информационных разрядов, всепроверочные разряды которой составлены в соответствии с формулой (2.36),является разрешенной кодовой комбинацией [я, Л]-кода.Пусть W и V - две разрешенные кодовые комбинации группового [п, А:]-кода.Тогда кодовая комбинация w = и + v также является разрешенной кодовойкомбинацией этого кода.
Действительно, еслии = a^a^...afi^b^,..b^, v = а\а[..м[Ь\Ь!^,.,Ь1,(2.37)тоW = (а^^а\) (а,+^;)...(а,+а;)(*,+ b\).,.(b^-^bl) = ау^..м-Ь\' V; ...6;,где(2.38)(2.39)Ь;=ЬлЬ; = с.^(а^ + а1) + ,..-^с/а,+а[Х А=1,2,...,г.(2.40)772. Основы телекоммуникацииТаким образом, проверочные разряды 6" кодовой комбинации w формируются в соответствии с выражением (2.40) и, следовательно, кодовая комбинация W является также разрешенной.Любые к линейно независимых векторов я-мерного линейного векторногопространства порождают Л-мерное подпространство, образуя базис этого подпространства. Отсюда следует, что для задания [«, ^]-кода достаточно выбрать к любых линейно независимых разрешенных кодовых комбинаций, а остальные разрешенные кодовые комбинации получать как линейные комбинациивыбранных базисных векторов.
Обычно для задания [л, Л]-кода используютэту возможность, 1федставляя А: линейно-независимых кодовых комбинаций в формематрицы. Такая матрица называется пороэюдающей матрицей [п, А:]-кода.В общем виде ее можно представить следующим образом:^пл =^ 12сг\к*11*12... h\rа21 а22*2к^21^22... h1г(2.41)акк ^к\ ^к2^кг'к\ *к2Очевидно, что порождающая матрица G^ ^ двоичного кода порождает ровно2* разрешенных кодовых комбинаций.В зависимости от выбранного базиса Л-мерного подпространства «-мерного кодового пространства кодовое расстояние совокупности 2* векторов ^-мерного подпространства может бьггь различным.
При проектировании \п,Щ -кодаставится задача оптимального размещения кодовых векторов в «-мерном кодовом пространстве в соответствии с заданной статистикой ошибок и, в частности, обеспечения максимально возможного кодового расстояния.Пусть Vj, v^,..., v^-кодовые векторы-строки, составляющие порождающуюматрицу(2.42)Gn^k =Тогда разрешенную кодовую комбинацию [«, Л]-кода можно представить ввиде линейной комбинации векторов:V = g,Vj + g^V^ +^Л'(2.43)где gj, ^25 —5 Sk ~ коэффициенты, принимающие значения из множества {0,1}.Проверочные разряды 6^,..., Ъ^ кодового вектора v = a^a^,.Mfi^b^„.b^, передаваемого по каналу связи, формируются в соответствии с правилом (2.36).782.2.
Методы защиты от ошибок и сжатия данныхЭто же правило можно использовать на приемном конце канала для проверкиправильности кодовой комбинации: равенство (2.36) должно вьшолняться, еслиошибки не произошло. Таким образом, с каждой принятой кодовой комбинацией можно связать систему проверок по числу проверочных разрядов, котораядля кодовой комбинации v = aj...a^6j...6^ описывается следующей системойуравнений:^с^а,-bCj2a2+... + %a^+6, =0;^21^1+^22^2 + - + ^ 2 .
t « ) t + * 2 = 0 ;^rl^l + С ^ г 2 ^ 2 + -(2.44)• + ^rit^it+*r=0-Здесь с. G{0, 1}, / = 1,..., г, у = 1,..., к. Нули в правых частях равенств истолковываются как отсутствие ошибки в принятой кодовой комбинации v.Для удобства систему проверок (2.36) обычно представляют в матричнойформе, а именно как произведение матрицы-строки v = || ау.м^Ь^„.Ь\\, соответствующей прршятой кодовой комбинации, на матрицу проверочных коэффициентов:Я.п,к'21-"Ik1 0 00 1 000'^rk01"12"U-22"^rl00(2.45)Матрицу Н^^, с помощью которой осуществляется система проверок надпринятой кодовой комбинацией, принято называть проверочной матрицей.Система проверок (2.36) над принятой кодовой комбинацией эквивалентнаее умножению на транспонированную проверочную матрицу Н^ ^.
Если ошибкинет, то должно вьшолняться равенствоV X н:0.(2.46)В общем случае результат умножения может быть отличен от нуля:II ^ r - V l - M I ^ Я;^^ = II Cr,C2...C....cJ|,(2.47)где с е {О, 1 } , / = 1,..., г.Матрица-строка || с^...с^||, полученная в результате умножения, называетсясиндромом ошибки. Всего может быть (2'" ~ 1) различных ненулевых синдромов, разбивающих множество возможных ошибок на {Т- 1) класса. Это позволяет по виду синдрома ошибки определять, к какому классу относится ошибка. Часто [п, А:]-код проектируется таким образом, что с вероятностью, близкойк единице, каждый из вьщеленньпс {!''- 1) классов ошибок содержит всего поодному элементу.
Такие коды позволяют исправлять ошибки.792. Основы телекоммуникацииРассматривая разрешенную комбинацию [п, А:]-кода как линейную комбинацию кодовых вектор-строк порождающей матрицы и подставляя выражение(2.43) в равенство (2.46), получаем+ g,(v^xHl,)+ ... + g/v,, V X Hi,) = 0.(2.48)Из этого выражения очевидно: чтобы для любой разрешенной кодовой комбинации [п, ^]-кода выполнялось равенство (2.46), необходимо и достаточно,чтобы вьшолнялось равенство:X Н1,= 0,илиС„,хН1,=0.(2.49)Это равенство устанавливает связь между порождающей и проверочнымиматрицами [«, А:]-кода, и по нему можно определить одну из них, если известнадругая.Если к какой-либо строке v.
порождающей матрицы G^^ прибавить линейную комбинацию других строк, то от этого она не изменится (в том смысле,что останется порождающей матрицей того же самого [п,к]'Кот). Действительно, пусть строка v. матрицы G^^ заменена строкой УД являющейся суммойстроки у и линейной комбинации других строк:v; = a,v, + a,v, + ... + v,.+ ...
+ a,v,.(2.50)Посмотрим, какое влияние оказывает такая модификация порождающейматрицы на общий вид разрешенной кодовой комбинации. Запишем разрешенную кодовую комбинацию в общем виде:v = g,v, +^2^2 + ... +g.y.+ ... + g,y,,(2.51)где^. е {О, 1 } ; / = 1,2,..., Л.После замены строки у на строку у/ получаем:V = g,v, + g^v^ + ... + g.(a,y, + a^v^ + ... + v. + ... -+- a^v^) + ... + g^v^ == (g, + g^ciX + (^2 -^ ЯЛ>2 + - + g.^i + - + (gk + gPkK(2.52)Так как коэффициенты (g^ + g.a) e{0, 1}, у = 1,2,..., к, то общий вид разрешенной кодовой комбинации не изменился и матрица с новой строкой У/ порождает тот же самый код.
Отсюда следует, что при сложении попарно, по три, почетьфе и т. д. кодовых комбинаций и записи полученной суммы на место одного из слагаемых изменяется лишь вид матрицы, но не затрагивается ее сущ802.2. Методы защиты от ошибок и сэюатия данныхность, т. е. матрица, претерпевшая указанную операцию, порождает тот женабор разрешенных кодовых комбинаций, что и исходная матрица.Путем замены строк матрицы О^^ъ соответствии с формулой (2.52) можноот любого ее вида перейти к каноническому виду:1 0 .
.. 0 Ъи0 1 .. 0<J^«,t6,2Ьгг*22^2гК^ Кг''кгк=00 .. 1(2.53)Здесь информационные разряды в порождающей матрице канонического видапредставлены единичной подматрицей.Пусть подматрица информационных разрядов порождающей матрицы имеет вид:а.а 12а.А^а 21а 22а 2ка к\ а к2а кк(2.54)Здесь все вектор-строки линейно независимы. Предположим, что это нетак и существует строка v., которая может бьггь выражена в виде линейнойкомбинации остальных строк.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
