Розділи про передачу інформації та коди захисту від помилок у кодуванні (компіляція) - PDF

ЗМІСТ (вибір заголовка) Типи помилок: характеристики порушень (шум) БЛОКОВІ КОДИ Здатність виявляти/виправляти помилки Прості коди товару Коди Хеммінга Загальні коди товарів Одинична помилка недвійкові корекційні коди Алгебраїчні елементи кодів захисту від помилок лінійні коди блоків та груп Модифіковані лінійні коди Циклічні коди Коди BCH Виправлення двох помилок Помилки випадків (сплеск) Коди проводів: визначення Коди з чергуванням Визначення кодів BCH Коди Ріда-Соломона Декодування алгоритмів для кодів BCH Виправлення видалень Максимальне КОНВОЛЮЦІЙНІ КОДИ Декодування (Розшифровка Вітербі) с.3 7 3 4 8 9 7 49 6 76 86 9 95 97 4 5 63 65

.9.8 Е н т ро п е, к а п а ц і т 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) + буде числом, яке не ділиться на жодне pi. Отже, або 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% надмірності. Інші обмеження на мінімальну відстань Верхня межа Макеліса-Родеміча-Рамсі-Велча (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, відповідно 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 k. 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; Консультативний комітет 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). Два мінімальні многочлени мають градуси не більше 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) = =