С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (1127136), страница 11
Текст из файла (страница 11)
Декодирование (n, k, d)-кода основанона :•разбиении единичного куба вп н адержащих шары радиуса r==k областей , соl (d - 1) /2 J с центрами в кодовых словах;•предположении , что произошло ~r ошибок.Задача о нахождении ближайшего кодового слова(общий случай) является N Р-трудной.Блоковый (п,кодированиеиизбыточ ностьk) код: два этапа декодированияvошибка+еwдекод . - 1ближ .
код.декод . -2_vсловоудаление избыт._и1-й этап: Восстановление переданного кодового словаv как ближайшего кw в метр ике Хэмминга -н ахождение центра соответствующего ш ар а.Для этого надо , вообще говоря, пер ебрать всестрок в12n х k-таблице2nкодовых слов .Известны , однако , т.н. <<Экспандерные>> коды с линейной сложностьюдекодирования, для которых неизвестны субква.дратичные алгоритмы кодирования, но это- исключение.
Они дают лучший из известных компромиссов между скоростью кодадекодирования.k/n, кодовым расстояиием d и быстротой3.1 . (IIIпоток) Коды, исправляrощие ошибки11 7Если расстояние до ближайшего центра шара (кодового слова) превышает величинуl (d -1)/2 J,то при передаче произошло больше ошибок, чемможет исправить код и при декодирование необходимо выдать отказ .v исходного сообщения u2-й этап : Восстановление попутём удален ия проверочных бит.Вывод: декодирование блокового (n,.....да-k ) -кода общего ви-очень ресурсоемкии процесс, поэтому его исполь-зование таких кодов возможно лишь при небольтихзначенияхnОднако,иk.принявряддополнительныхний на множество кодовых слов,экспоненциальных требованийнениякодаипосложностипоможно перейти отпамятиалгоритмовния/декодирования к линейным поограничеnидляхракодироваk.Эти ограничения приводят к использованию блоковых кодов специального вида : групповых, а из групповых-циклических.Чтобы построить код максимального размера, исправляi-ощий rкубвпошибок, нужно вложить в единичныймаксимально возможное число непересекающихся шаров радиусаВопрос:П ри какихnинепересекающиеся<< без зазоров»?задача nлomuou ynarx;oвrx;u .r rв куб вп можно уложитьшар ырадиусаr<< плотно>>,118 IIIпоток: Глава3.Коды, исправляrощие ошибкиОтвет: Такое удаётся в (нетривиальных) случаях:1)n2q - 1, r==1-rк;оды Хэммиrнга, у нихm=qи2)n=rк;од Голе.я, к него т=23 , r = 3 -11.Это совершен/Н/ьtе или эrк;стремалън/ые rк;о ды .Тривиальные коды :(п, О, О) -с 2п кодовыми словами ;•• (2r+ 1, 1, r)-с повторением нечётной длины ;(п, О, п).•Тео емачисло3.1 (Хэ мминга).
При 2r < n .маrк;сималъпоеt rк;о до вых слов паходитс.я в пре делах2по2п12сп + сп + . . . + спrДоказа тельство .t~t~о1сп + сп + .. . + с~есть максимальное число непересекающихся ш аров радиусаr,помещающихся в кубе вп.Верхняя оценка (граница Хэмминга)усаr.содержит точки :- шар радисам центр + все точкис од-u... , r измене нны ми координатами, т.
е . всегос~ + с~ + ... + с~ штук и шары не пересекаются .но и, двумя,Для оценки снизу построим негрупповой код :1)берем произвольнуiо точку вп и строим вокругнеё шар р адиуса2)2r ;берем произвольную точку вне построенного шара и строим вокруг неё шар радиуса2r;3) и т.д., каждая новая точка выбирается вне построен ных шаров .3.1 . (IIIпоток) Коды, исправляrощие ошибки119В р езультате :•шары ,возможно,пересекаются,...но каждыишарзанимает с~ + с~ + ... + c;r точек ::::} шаров неменее 2n/ (с~+ с~+ ...
+ c;r);•шары р адиуса r с центрами в выбранных точкахне пересекаются .оПостроение кода ХэммингаПо кажем , что в случае nn:=:2q - 1, r :=: 1.2q - 1 получим t:=::=:~~,1т.е . верхняя оценка в теореме Хэмминга достигается .Построим код, а потом определим его кодовое расстояние . Рассмотрим таблицу :100 ...
000010 ... 000001 ... 000k = 2q- (q+ l )• •1100 . .. 0001010 ... 0001001 ... 000•• • •000 ... 100000 ... 010000 ... 0011111 ... 1011111 ... 1101111 ... 111k = 2q- (q+l )q=mСлева - единичная матрица порядка 2q- 1 справа - все бинарные н аборы длиныне менее двух еди ниц .q),q, содержащие120 IIIпоток: ГлаваКоды, исправляrощие ошибки3.Пр осуммировав всевозможные совокупности строктаблицы, получим t2 k == 2 2q-(q+ l) различных ко-==ДОВЫХ СЛОВ, НО==t22q-(q+ l )22q- 1==+2q1 nН айдём кодовое расстояние построенного кода:•в каждой строке таблицы•если сложитьдве строки-не менеев левой части будет-23един иц ;единицы , ав правой - хотя бы 1,не менее трёх строк - в левой части будет не менееТ.
е. всегда р3единиц.а,(3? 3 =>шары единичного р адиусас центрами в полученных наборах не пересека1от ся .== 3,Пример 3.2 (код Хэмминга длины 7) . Имеем q== 7, k == 23 - (3 + 1) == 4.данного парамет ра q == 3 составимn == 23Для-1Хэмминга:1оооСкладывая пооотаблицу кода1 1 о1 о о 1 о 1о 1 о о 1 1о о 1 1 1 1mod 2овсе совокупности приведённых 4 строк (вкл1очая пустуFо), получаем 24личных бинарных слов длиныкодировать16которыми можно за14;исправляетслову веса О и7,по71 ошибку, обнаруживает2- , 5- , 6- кратные ошибки и 80% 3- и 4- кратных.3иразсообuцений .Этот код содержит послов веса7,== 163.1 .
(III поток)Коды, исправляrощие ошибки121Число кодовых слов кода Хэмминга с различнымивесами есть коэффициенты производящего полпомаW( z) ==1n+1Н апример, дляW( z) ==(1 + z)n + n(1 + z )18n==7n- l2(1 - z)2•получим743[(1 + z) + n(1+ z) (1 - z)==т. е . уже известные значениядовых слов веса О,n+l3, 4и7]341 + 7z + 7z + z1, 7, 7и17,для числа косоответственно.Является ли кодом Хемминга тривиальный(3, 1)-код?Марсе.лъ Го.лей(Marcel J. Е. Golay, 1902- 1989)-швейцарский математик и физик.В своей единственной работе по теорииинформации....(1949) предложилvvсовершенным двоичным код, исправляющим триош ибки.В ходе космической программы С ШАВо.ядж ер(1979-81) для передачицветных изображений Юпитераи Сатурна и спользовался код Голея .122 IIIпоток : ГлаваКод Голеячто3.Коды, исправляrощие ошибки(23, 12, 7) -код.М .
Галей обнаружил ,сgз + Сiз + СJз + СJз == 2объём шара радиуса11·3Это позволило предположить , что существует совершенный содержащий==212==4096кодовых слов совершенный (23, 12, 7)-код , исправляющий до3ошибок, и М . Галей в своей статье указалтакой код .Доказано , что других пар(п, r), удовлетворЯIQЩИХусловиюс~+... + с~- целое,кроме(2q - 1, 1) - код Хэмминга и тривиальных(п, 0), (n, n), (2r + 1, r), r == 1, 2, .
. . не существует.3. 2Линейные кодыЛинейные коды: определение, свойстваВ олыпаяпостроенанаализовыватьчастьтеорииt/линеин'Ыхблоковогокодах,эффективныекодированияпозволяющихалгоритмыре-кодирования/ декодирования. В двоичном случае их называютгруппов'Ы.ми, т.
к . они обр азуют группу относительнооперации «сумма поm od 2».3.2.(IIIпоток) Коды, исправляrощие ошибкиУтве ж ение3.2.+mod 2)(сумма по123Устойчивая оm'!-lо сителъ'Н о оп ерациисовоrх;уп'Ностъ rх;одовых слов С обра зует группу .Доказа тел ьство.Устойчивость ......,(предполагается) :слов а,f3для любыхкодовых,_.._.Е С выполняется а ЕВАссоциативность:f3= -;у Е С;свойство операции ЕВ;......,Существование0:а ЕВ а =(О,Противоположные элементы:... , О)-а ==О Е С;а - см.
выше.DТео ема 3.2 (свойство кодового расстояния групп ово гокода). Кодо в о е рассто.я'Ниеd = min~ра,df3группового rх;ода рав'Но=f3 и -;:;; -m1n~,,;:у=/= ОCi=/=(3г де а,•rх;одовые слова из с.Доказательство. Для произвольных кодовых слов а ивсегда сущест в ует их сумма......,причем -;:;;#о при а-кодовое словоf31:......,# f3.Отсюда получаем оценку•m1цра, /31-;:;; ,;:у=/=ОCi=/=(3которая достигается , например , при): mi!_lf3= О.D124 IIIпоток: Глава3.Коды, исправляrощие ошибкиСле ствие. Для вычисления подового расстояния группового пода достаточно перебратъ 2k-1 подовъtх слов.{0, 1 }n == вп есть п-мерное координатное векторноепространство над конечным полем IF 2 == {О , 1}.Определение3.3.
Блоковый (п, k) -код С называетсялинеuнъt.м, если он образует векторное подпространстворазмерностиkкоординатного пространства вп.Это озн ач ает, что в линейном коде С-1) сумма любых кодовых слов - кодовое слово, т.е.это групповой код;2) кодовое расстояние d == min -;у ;1ЕС3) существует базис { 9о, 91 , ...
, 9 k- l} из k векторов 9 i Е вп, i == О, ... , k - 1, и любой векторvЕ С может быть представлен какk-lv ==LUi9 i'UiЕ {о ' 1}.i=OПорождающая и проверочная матрицы.Линей-ный код: матричное пред·ставлениеk- lv ==Li=OПримерUi 9 iСи , где Gnxk-== [9о 91· · · 9 k- l ]порождающа.я .матрица кода .3.3 ( (7, 4)-код Хэмминга). Ранее была получена таблица , сложением строк которой получаr-отся все24 == 16 кодовых слов.
Порождаr-ощая матрица получается транспонированием этой таблицы:3.2.(IIIпоток) Коды, исправляrощие ошибки1оооо1оооо1о-11 1 о 11 о 1 1о 1 1 1оG7 x4оо125порождающая мат рицав cucmeмamurчecnou форм е :п ри кодировании исходны есообщения помещаются впервые4бита кодового словаПpoв ep ottt'!-la.я .матрича H mxn, т ~n - kдля линейного(n, k) -кода обладает свойством Hv ~ О длялrобого кодового слова v.Пусть Ik и Im - единичные мат рицы порядков k ит соответственно .
Тогда если по рождаrощая матрицаIkимеет вид G ~0,то матрица Н ~ [P mxkГ mxkIm]будет проверочной.Пример 3.3 (продолжение- (7, 4)-код Хэмминга) . Дляпостроенной порождающей матрицыG 7 x4проверочной будетНзх71 1 о 1 1 о о1 О 1 1 О 1 Оо 1 1 1 о о 1Упражнение: Закодируйте матрицей4-битное сообщение, получив кодHvv,Gкакое-нибудьи убедитесь , что~ О.Характеристики кода Хэмминга :•Код содержащийn~2m - 1,q~ т проверочных бит, длиныисправляющий одну ошибку.126 IIIпоток: ГлаваСовершенный•нуюt ==3.кодупаковку :2n;1Коды, исправляrощие ошибкиосуществляетразбивается на22m- (m+ l ) шаров радиуса r == 1==кубплот-B 2m_ 1с центрами в кодовых словах.•Скорость кода-•Столбцы проверочной матрицывекторы из•R == 1 - 2:!~ 1 .-все ненулевые2m.Историческая справка .
П ервой ЭВМ , в которойиспользовался код Хэмминга, быластроенная вIBM 7030 , по1960 г. (через 10 лет после появления кода Хэмминга) . До этого в ВТ использовался лишь простейший способ повышения надежности3.3-••провер']);а на 'ltemнocmъ.Кодирование линейными кодамих;одированиеиvизбыточность==GuН аиболее удобно систе.матичес']);ое или разделимоекодирование, при которомkбит сообщения копируiотся в заранее фиксированные позиции кодового слова .Такая возможность основана н а том, что матрицаGопределена с точностью до экв ивалентн ых преобразований столбцов (переход к другому базису того жекода).Пример3.4 (систематического (разделим ого) кодирования) .Пусть линейный код заданпорождающей матрицейG.3.3.(III1.Споток) Коды, исправляrощие ошибкипомощьюэквивалентных127преобразованийстолбцов матрицаGкотором первыестрок образу1от единичну1о матрицуkможет быть приведена к виду, вI k:-~> Gnxk2.Тогда кодированиеским : первые==v == Guбит кодового словаkбудет систематичеvявляются битамиИСХОДНОГО СООбЩеНИЯ U .Вопрос: что произойдёт при перестановке строк кодирующей матрицы?Ответ: Будет задан другой линейный код (другиенаборы из вп будут кодовыми словами).П ри систематическом кодировании2- й этап декодирования (удаление избыточности) становится тривиальным.Ортогональное дополнение к подпространству кода.Итак, С-k-мерное подпространство{0, l}n ==вп.Элементы вп, ортогональные ко всем элементам С, образуют ортогоналъное подпространство cj_:\1 V \1сс1.W : VT Х W==Q.Замечания:• J& == fli~ cz + fli~с-:, ;пkm=n- k-•сuвп' т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
