Глави за предаване на информация и кодове за защита от грешки при кодиране (компилация) - PDF
СЪДЪРЖАНИЕ (избор на заглавие) Видове грешки: характеристики на смущения (шум) БЛОКОВИ КОДОВЕ Възможност за откриване/коригиране на грешки Прости кодове на продукти Кодове на Хаминг Общи кодове на продукти Единична грешка небинарни коригиращи кодове Алгебрични елементи за кодове за защита от грешки Кодове линейни блокови и групови кодове Модифицирани линейни кодове Циклични кодове BCH кодове Коригиране на две грешки Инцидентни грешки (спукване) Тел кодове: дефиниция Преплетени кодове Определение на 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 ie C a p a c it a t e.7.6.5.4.3. 3.4.5.6 R a t a e r o r il o r. 7.8.9 Капацитетът на симетричен двоичен канал (BSC) е много лесен за изчисляване, но много труден за постигане. Изразът за капацитета на канала е C (ε) = H (ε) и H (ε) = ε logε (ε) 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 Случайни битови грешки Позоваването на случайни грешни битове включва двоичен канал с независимо разпределени грешки (iid независими идентично разпределени), с други думи симетричен двоичен канал. Симетричен двоичен канал има единичен параметър на шума, ε: 3
Евклид показа, че простите числа са безкрайно много. Демонстрацията се прави чрез свеждане до абсурда. Прието е, че ще има само ограничен брой премии. Тогава m = (p p pt) + би било число, което не се дели на нито едно пи. Така че или m е просто, или m има главен делител, който трябва да се различава от всеки pi. Въпреки че няма проста формула за първото 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. Умножавайки равенството с a 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,96,96,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 * двоичен код на Golay: q =, n = 3, k =, t = 3 Тернален код на Golay: q = 3, n =, k = 6, t =. Кодовете на Golay датират от 949 г. Квази перфектни кодове 6
Пример за съкратен код Матрицата за систематична проверка на паритета за двоичен код на Хаминг (5,) е H = Този код може да бъде съкратен до (, 8) чрез изтриване на колоните с максимално тегло, до 4. H = Съкратеният код може да коригира грешки на един бит в 8-битова информационна дума. Всяко уравнение за проверка е изключително 5- или 6-битово, по-малко от 8 записа в оригиналния код. Удължени кодове Удължение: запазете n k, увеличете k, съответно n. Въвеждат се допълнителни информационни символи и се включват в уравненията за проверка. Удължаването е трудно постижимо без намаляване на минималното кодово разстояние. Пример: Разширени кодове на Рийд-Соломон, получени чрез удължаване на кодовете на Рийд-Соломон (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). (a, a) (b, b) = (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). Съкращение: CRC Cyclic Redundancy Check; Консултативен комитет на CCITT по международни телефони и телеграфи 9 9
Нека α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). Двата минимални полинома са с градуси най-много m. По този начин степен m. H има две линии с елементи от GF (m), еднакви с m линии над GF (). Следователно броят на битовете за проверка отговаря на връзката nk m. Факт: Ако m 3, тогава nk = m. Синдроми за BCH кода, коригиращи две грешки Помислете за модел на грешка на теглото: e (x) = xi + xi, i r + Упражнение: Възможността за откриване на случайни грешки за блоков код (n, k) е най-много n k. Характеризиране на кодове за корекция на грешки при девиз Девиз: Блоковият код може да коригира всички инциденти с дължина не повече от l, ако и само ако никога две думи от кода не се различават от сумата от два инцидента с дължина най-много l.
<> 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 ( х)) имат коефициенти от подтела. GF () = = GF (4) = =