Поглавја за пренос на информации и кодови за заштита на грешки при кодирање (компилација) - PDF
СОДРИНА (избор на наслов) Видови грешки: карактеристики на нарушувања (бучава) БЛОК-КОДИ Способност за откривање/корекција на грешки Едноставни кодови на производи Кодови за зачувување Општи кодови на производи Единствена грешка небинарни корективни кодови Алгебарски елементи за кодови за заштита од грешки линеарни блокови и групни кодови Изменети линеарни кодови Циклични кодови Две корекции на грешки BCH кодови Грешки во инцидентот (рафал) Wireични кодови: дефиниција Прелиени кодови Дефиниција на BCH кодови Рид-Соломонски кодови Алгоритми за декодирање за BCH кодови Корекција на бришења Максимални СЛЕДНИ КОДИ Безбедно декодирање (Декодирање на Витерби) стр.3 7 3 4 8 9 7 49 6 76 86 9 95 97 4 5 63 65
.9.8 E n t ro p т.е C a p a c it a t e.7.6.5.4.3. 3.4.5.6 Капацитет на симетричен бинарен канал (BSC) е многу лесен за пресметување, но многу е тешко да се постигне. Изразот за капацитетот на каналот е C (ε) = H (ε) и H (ε) = ε logε (ε) лог (ε) е бинарна ентропска функција. H (ε) е мерка за количината на информации или несигурност при бинарна одлука со априори веројатности ε, ε. Покрај него има закривени податоци што претставуваат капацитет и ентропија со различна стапка на погрешни битови. Придружната табела нумерички ги илустрира двете функции, H (ε) и C (ε). Погрешна брзина на бит (ε) 3 4 5 6 7 8 9 H (ε), 4689955935893,8793358959,477577375,47333583,85383,37469,46969,88,334 C (ε), 5344647,9968644,98859465,99856966477,999 99999753388,99999979888,9999999686599 Случајни битни грешки Упатувањето на случајни погрешни битови вклучува бинарен канал со независно дистрибуирани грешки (доколку е независно идентично распореден), со други зборови симетричен бинарен канал. Симетричен бинарен канал има единствен параметар на бучава, ε: 3
Евклид покажа дека простите броеви се бесконечно многу. Демонстрациите се прават со редукција на апсурд. Прифатено е дека би имало само конечен број на премии. Тогаш m = (p p pt) + ќе биде број што не се дели со ниедно пи. Значи или m е прости или m има главен делител кој треба да се разликува од кое било пи. Иако не постои едноставна формула за првиот x, теоремата на прости броеви вели дека: Бројот на прости прсти помали од x, π (x) е околу x/lnx. Поточно, π (x) со x. Факт демонстриран од Бертранд: За секој цел број n, помеѓу n и n, постои прости. Особено, има барем прости од m битови за кое било m Кога d> не е фактор на n, поделбата n со d произведува остаток не нула. Алгоритмот за поделба го изразува делителот n како збир на повеќекратно qd на делителот d и мал остаток r: n = qd + r со r m, тогаш барем едно поле мора да содржи повеќе од еден објект. 3
Бројот на елементи на соодветна подгрупа H ја задоволува нееднаквоста, со i првиот експонент за кој се појавува повторувањето и n најмалиот број за тоа i. Множејќи ја еднаквоста со i = (ai) добиваме e = an. Така, подгрупата генерирана од е. ai j i j i j Ако i, j t грешки] 5.4 . 3 3. 4 3.5 5 3.3 6.6 7.8 8
6 8 3 3 4 57 7 88 6385 64 646 643.966.966.958.955. 9 5.5.5. 3 Колку бита на заштита се потребни за сигурна комуникација? Ограничувањето на Хаминг покажува дека се потребни повеќе од 4% од вишокот за да се постигне разумна стапка на грешка по бит. Други ограничувања на минималното растојание Горната граница McEliece-Rodemich-Rumsey-Welch (MRRW) R H (, 5 δ (δ)) каде што H е функција на бинарна ентропија и δ = d */n е нормализирано минимално растојание. Горна граница на плочки за линеарни бинарни блокови кодови (вежба): n k d * k d = d */n, 5 за големи k. Долната граница на Варшамов-Гилберт за бинарни блок-кодови. Ако d * Бинарен код на голај: q =, n = 3, k =, t = 3 Крој на тројни голај: q = 3, n =, k = 6, t =. Гола кодовите датираат од 949. Кваси-совршени кодови 6
Пример на скратен код Систематската матрица за проверка на паритет за бинарен код за зачувување (5,) е H = Овој код може да се скрати на (, 8) со бришење на колоните за максимална тежина, на 4. H = Скратениот код може да ги исправи грешките на еден бит во 8-битен информативен збор. Секоја равенка за верификација е ексклузивна 5- или 6-битна, помалку од 8 записи во оригиналниот код. Издолжени кодови Издолжување: задржете n k, зголемете k, соодветно н. Воведени се дополнителни симболи за информации и вклучени во равенките за верификација. Издолжување е тешко да се постигне без да се намали минималното растојание на кодот. Пример: Продолжени кодови на Рид-Соломон, добиени со издолжување на кодовите на ReedSolomon (Q, k) до (Q +, k +) со додавање на две колони лево од матрицата H. Од H = α α α α4 α d α d α Q α (Q) d (Q) α преминува во H = α α α α4 α d α d α Q α (Q) d (Q) α Објавени кодови Прочистување: чувај n, одзема k и зголемувај n к 6
3 4 5 6 7 8 α α = α + α + α = α + α + α = 3α + = α α = α + α + α = 4α + = α + α + α = 3α + = Како што се очекуваше, α 8 =. Множителот на α е 8. Множење и поделба во GF (9) Производот на елементите a = a + aα и b = b + bα во GF (9): (a + aα) (b + bα) = ab + (ab + ab) α + abα = = ab + (ab + ab) α + (abα + ab) = (ab + ab) + (ab + ab + ab) α (Изразот се користи и за GF (4), но тука множењата а склоповите се модул 3). (а, а) (б, б) = (ab + ab, ab + ab + ab) Вежба: Пронајдете ја формулата за реципроцитет (a + aα) = (b + bα). Совет: Еден од можните третмани: решавање на системот во b и b ab + ab = ab + (a + a) b = аритметика во конечното поле GF (6) Постојат три главни полиноми на степен 4 над GF (): x4 + x +, x4 + x3 +, x4 + x3 + x + x + Наједноставниот е x4 + x +. Нека α е елемент што ги задоволува α4 + α + = α4 = α +. Моќноста на α може да биде колона на матрицата за проверка на паритет, во систематската верзија. H = Во GF (6), користејќи α4 = α +, компонентите на производот y = ab се: y = ab + ab3 + ab + a3b y = ab + ab + ab3 + ab + a3b + ab3 + a3b y = ab + ab + ab + ab3 + a3b + a3b3 y3 = ab3 + ab + ab + a3b + a3b3 Основната теорема на алгебрата 7
Лема: Нека f (x) е полином над GF (q) GF (Q). Елемент β во GF (Q) е нула од f (x) ако и само ако x β е делител на f (x) над GF (Q). Доказ: Со алгоритмот на поделба f (x) = q (x) (x β) + r (x), со степен тогаш редоследот на αi е (q)/d и имплицитно n k за кој g (x) (xn). Акроним: Проверка на ЦКК цикличен вишок; Консултативен комитет на CCITT за меѓународен телефон и телеграф 9 88
Α3 нека биде избраниот елемент. Овој навидум очигледен избор работи многу добро. Матрицата за проверка на паритетот претставена над GF (m) е α α α n H = 3 α 6 α 3 (n) α Кодните зборови дефинирани од H се полиноми c (x) со нули во α и α3. Така, секој збор од кодот е множител од минималните полиноми на α и α3. Нека f (x) и f3 (x) бидат овие минимални полиноми над GF (). Полиномот на генераторот е g (x) = f (x) f3 (x). Двата минимални полиноми се со степени најмногу м.Така, степенот м.Х има две линии со елементи од GF (m), исто со m линиите над GF (). Затоа, бројот на битови за верификација ја задоволува релацијата nk m. Факт: Ако m 3, тогаш nk = m. Синдроми за кодот BCH што корегираат две грешки Разгледајте модел на грешка во тежината: e (x) = xi + xi, i r + Вежба: Способноста да се откријат случајни грешки за блок-код (n, k) е најмногу n k. Карактеризација на кодовите за корекција на грешки во инциденти Мотото: Блок-кодот може да ги коригира сите инциденти со должина не повеќе од l ако и само ако никогаш два збора кодови не се разликуваат со збирот на два инциденти со должина најмногу l. 94
<> d * = 5 бара 4 моќност. Конјугирани експоненти. d * = 9 бара 8 моќ. Експоненти 4 конјугати. d * = бара напојување. Експоненти 7 конјугати. d * = 4 потребни се 3 моќи. Конјугирани експоненти, но подобри 7 конјугати (прочистениот код е изнесен). GF (56): моќта на примитивниот елемент Азбука на декодерот GF (56) Примитивните BCH кодови во тесна смисла, исправувајќи две грешки над GF (), GF (), GF (4), GF (8) може да се дефинираат со o иста матрица за проверка на паритет: H = α α α3 α4 α α α α 4 6 8 α 54 α 58 α 75 α 6 Генерирање полиноми lcm (f (x), f (x), f3 (x), f4 ( x)) имаат коефициенти од под-тела. GF () = = GF (4) = =