Теорія кодування

Шрифт Брайля — типовий приклад коду, який використовує стиснені дані на певній відстані, щоб компенсувати помилки і втрати часу при читанні.

Теорія кодування — це вивчення властивостей кодів та їхньої придатності для виконання специфічних задач. Коди використовуються для стиснення даних, криптографії, знаходження і виправлення помилок, передачі та зберігання даних, і від недавнього часу — для мережевого кодування. Коди вивчаються у теорії інформації, електротехніці, математиці і кібернетиці для створення ефективних і надійних методів перетворення даних. Зазвичай процес кодування включає усунення надлишку даних та виправлення або виявлення помилок у даних, що передаються.

У теорії кодування існують чотири основні методи обробки інформації:

1. Стиснення даних, або source coding — кодування джерела;
2. Попередня корекція помилок, або пряма корекція помилок (також використовують термін англ. channel coding);
3. Криптографічне кодування;
4. Лінійне кодування.

Кодування джерела спрямоване на стиснення даних для їхньої ефективнішої передачі. Ця практика зустрічається кожен день в Інтернеті, де стиснення даних використовується для зниження навантаження на мережу та з метою зменшення розміру файлу.

Наприклад, стиснення даних Zip робить файли даних меншими для таких цілей, як зменшення Інтернет-трафіку. Стиснення даних та виправлення помилок у такому випадку можуть застосовуватися одночасно.

Виправлення помилок додає додаткові біти даних, щоб зробити передачу даних, присутню на каналі передачі, стійкішою до перешкод. Звичайний користувач не має уявлення щодо багатьох додатків, які використовують кодування каналу. Для запису типового музичного компакт-диску (CD — [сіді́]), пошкодженого подряпинами чи спотвореної пилом використовується код Ріда-Соломона (англ. Cross-interleaved Reed–Solomon coding, CIRC) для корекції інформації, що на ньому. Навіть якщо пошкоджено значний обсяг інформації, зіпсовано кілька секторів дискового носія, то код Ріда — Соломона дозволяє відновити велику частину втраченої інформації. У цьому додатку каналом передачі є сам CD.

У стільникових телефонах також використовується метод кодування для корекції завмирання і шуму високої частоти передачі радіосигналу.

Модеми даних, телефонні трансляції та «мережі глибокого космосу НАСА» (Deep Space Network National Aeronautics and Space Administration, DSN NASA) використовують канальні методи кодування, щоб отримати біти через, наприклад, турбо-код і LDPC коди.

Історія теорії кодування

двовимірна візуалізація відстані Геммінга

У 1948 році Клод Шеннон опублікував статтю «Математична теорія зв'язку» у Технічному журналі Bell System (Bell System Technical Journal). Ця робота присвячена питанню, як краще кодувати інформацію, яку відправник хоче передати. У цій фундаментальній праці автор використовував інструменти з теорії ймовірностей, розроблених Норбертом Вінером, які на той час перебували в стадії їх першорядних розрахунків і застосовувалися до теорії комунікації. Шеннон розробив інформаційну ентропію як міру невизначеності в повідомленні в той час, власне — це було винаходом області теорії інформації.

Двійковий код Голея був розроблений в 1949 році. Цей код корекції помилок може виправляти до трьох помилок в кожному з 24-бітному слові і виявити четверту^:26.

Річард Геммінг отримав премію Тюрінга в 1968 році за свою роботу в Bell Labs з чисельних методів, систем автоматичного кодування і виявлення помилок і кодів, що виправляють помилки. Він винайшов поняття, відомі як Коди Гемінга, віконна функція, числа Геммінга, і відстань Геммінга.

Джерело кодування

Метою кодування джерела є отримання вихідних даних та їх зменшення.

Визначення

Дані можуть розглядатися як випадкова величина: $X:\Omega \rightarrow {\mathcal {X}}$ , де $x\in {\mathcal {X}}$ з'являється з ймовірністю $\mathbb {P} [X=x]$.

Дані кодуються рядками (слів) в алфавітному порядку $\Sigma$.

Код є функцією $C:{\mathcal {X}}\rightarrow \Sigma ^{*}$(or $\Sigma ^{+}$ якщо порожній рядок не є частиною алфавіту).

Де $C(x)$ — це кодове слово, пов'язане з $x$.

Довжина кодового слова записується у вигляді $l(C(x))$.

Очікувана довжина коду $l(C)=\sum _{x\in {\mathcal {X}}}l(C(x))\mathbb {P} [X=x]$.

Конкатенації кодових слів $C(x_{1},...,x_{k})=C(x_{1})C(x_{2})...C(x_{k})$.

Кодове слово порожнього рядка є самим порожнім рядком: $C(\epsilon )=\epsilon$

Властивості

1. $C:{\mathcal {X}}\rightarrow \Sigma ^{*}$ є несингулярною, якщо ін'єкційна.
2. $C:{\mathcal {X}}^{*}\rightarrow \Sigma ^{*}$ є однозначно декодованою, якщо ін'єкційна.
3. $C:{\mathcal {X}}\rightarrow \Sigma ^{*}$ відбувається миттєвою якщо $C(x_{1})$ не є префіксом $C(x_{2})$ (і навпаки).

Правило

Ентропія джерела є мірою інформації. В основному, вихідні намагаються зменшити надмірність інформації, присутню в джерелі, і являють собою джерело з меншою кількістю бітів, які несуть більше інформації.

Стиснення даних, яке явно намагається мінімізувати середню довжину повідомлень, відповідно до певної стандартної моделі ймовірностей називається ентропійним кодуванням.

Різні методи, які використовують схеми кодування джерела, намагаються досягти межі ентропії джерела. C(x) ≥ H(x), де H(x) є ентропією джерела (швидкість), і C(x) — це бітрейт після стиснення. Зокрема, жодна схема кодування джерела не може бути кращою, ніж ентропія джерела.

Приклад

Факсимільний зв'язок використовує простий код довжини серії. Джерело кодування видаляє всі зайві дані для передавача, знижуючи пропускну здатність, необхідну для передачі.

Канальне кодування

Додаткові відомості: Виявлення та виправлення помилок

Мета теорії кодування каналу полягає у тому, щоб знайти коди, які швидко передаються, містять багато дійсних кодових слів і можуть виправити або принаймні виявити багато помилок. Хоча вони не є взаємовиключними, продуктивність кодування у цих сферах є компромісом. Таким чином, для різних областей застосування відповідно оптимальними є і різні коди. Необхідні властивості канального коду в основному залежать від ймовірності помилок, що відбуваються під час передачі.

У звичайному компакт-диску, погіршення якості інформації, що зберігається на ньому, в основному відбувається завдячуючи пилу або подряпинам. Компакт-диски використовують поперечно перемежоване кодування Ріда — Соломона для розповсюдження даних на диску. Отже, коди використовуються з чергуванням. Дані розкидані по всьому диску. Хоча це і не дуже прийнятний код, код з простим повтором може слугувати зрозумілим прикладом.

На прикладі, якщо взяти блок бітів даних (що представляє звук) і відправити його три рази. У приймальнику ми отримаємо біт з трьома повтореннями частинами і приймемо більшість звуку. Суть цього прикладу полягає в тому, що біти не просто надсилаються по порядку, а у їх чергуванні. Блок бітів даних спочатку ділиться на 4 менші блоки. Потім відбувається проходження циклу по блоку і відправляється один біт з першого, потім другого і т. д. Це робиться три рази, щоб розподілити дані по поверхні диска. У контексті коду з простим повтором це може виявитися неефективним. У випадку, коли використовується цей метод чергування існують більш потужні коди, які ефективніші для виправлення помилки «сплеску» (burst), подряпин або пилової плями.

Наприклад космічний зв’язок у глибині космосу обмежений тепловим шумом приймача, сигнал якого радше безперервний, ніж переривчастий. Подібно до цього, модеми з вузькосмуговим діапазоном частот обмежені шумом, що присутній в телефонній/стільниковій мережі, а також змодельовані практичніше щодо безперервного сигналу^:26. Натомість у стільникових телефонів присутнє швидке затухання сигналу. Використовувані високі частоти можуть спричинити швидке згасання сигналу, навіть якщо приймач переміщений на кілька сантиметрів. Знову ж таки, існує клас канальних кодів, призначених для боротьби із згасанням сигналу^:26:21.

Лінійні коди

Термін алгебраїчна теорія кодування позначає підполе теорії кодування, де властивості кодів виражаються алгебраїчними термінами, а потім досліджуються далі. Теорія алгебраїчного кодування в основному поділяється на два основних типи кодів^:22.

Алгебраїчна теорія кодування в основному ділиться на два основних типи кодів:

1. Блоки лінійних кодів;
2. Згорткові коди.

Вона аналізує наступні три головні властивості коду:

• довжина кодового слова;
• загальна кількість дійсних кодових слів;
• мінімальна відстань між двома дійсними кодовими словами, використовуючи в основному відстань Геммінга, а іноді і інші відстані, як відстані Лі.

Блоки лінійних кодів

Блоки лінійних кодів мають властивість лінійності, тобто сума будь-яких двох кодових слів також кодове слово, і вони застосовуються до вихідних бітів в блоках, звідси і назва лінійних блокових кодів. Є блокові коди, які не є лінійними, але це важко довести, що код є хорошим без цієї властивості. Блоки лінійних кодів наведені їх символами алфавітів (наприклад, двійковими або трійковими) та параметрами (n,m,d_min), де

1. n — довжина кодового слова, в символах,
2. m — це число вихідних символів, які будуть використовуватися для кодування відразу,
3. d_min — мінімальна відстань Геммінга для коду.

Є багато типів лінійних блокових кодів, такі як:

1. Циклічні коди (наприклад, коди Геммінга)
2. Біт парності
3. Поліноміальні коди (наприклад, коди БЧХ (BCH))
4. Коди Ріда-Соломона
5. Алгебраїчно-геометричні коди
6. Коди Ріда-Мюллера
7. Ідеальні коди

Блок коди тісно пов'язані з проблемою «Задача про пакування куль», до якої була привернута увага багатьох математиків та спеціалістів у цій сфері протягом багатьох років. У двох вимірах, це легко візуалізувати. Взявши купу монет однакового діаметру на столі і зсовуючи їх до купи, в результаті має скластися картина шестикутника у вигляді бджолиних стільників. Але блокові коди залежать від більшого числа вимірів, які не можуть легко бути візуалізованими. «Потужний» (24,12) код Голея, який використовується для далекого космічного зв'язку використовує 24 вимірювання. При використанні як двійкового коду (який, як правило, є) розміри відносяться до довжини кодового слова, як визначено вище.

Теорія кодування використовує N-мірну модель сфери. Наприклад, скільки монет однакового розміру можуть бути укладені в коло на столі, або в 3-х вимірах, скільки кульок певного діаметру можуть бути упаковані в кулю, діаметром із нашу Землю. Інші міркування передбачають вибір коду. Наприклад, при укладці шестикутної тари в обмежений простір прямокутної коробки залишиться порожній обшар в кутах. Із збільшенням корисного об'єму, відсоток порожнього простору стане все меншим. Але за умови, що тара, яка поміщена в середину прямокутної коробки прийме об'єм максимально наближений до об'єму коробки, — по аналогії «корисного об'єму» поєднання кодів буде мати значення «досконалих» кодів. Єдиними нетривіальними та корисними досконалими кодами є коди Геммінга на відстань-3 із параметрами, що задовольняють умову: (2^r — 1, 2^r — 1 – r, 3); а також [23,12,7] двійковий і [11,6,5] трійковий коди Голея.

Іншою властивістю коду є кількість сусідів, яку може мати одне кодове слово. Знову ж, розглянемо копійки, як приклад. Спочатку укладаємо монети в прямокутну решітку — кожна копійка матиме 4 суміжних сусіда (і 4 у кутах, що знаходяться далі). У шестикутнику кожна копійка матиме 6 суміжних сусідів. За умови збільшення площі прямокутної решітки, кількість найближчих сусідів дуже швидко збільшиться. В результаті значно зросте і кількість способів для утворення шуму, яка змусить приймач обирати сусіда (отже, помилка). Це фундаментальне обмеження блокових кодів, та й взагалі всіх кодів. Можливо, важче спричинити помилку одному сусіду, але кількість сусідів може бути досить великою, тому загальна ймовірність помилки зростає, від чого зазнає втрат цільність і суть коду як такого.

Властивості лінійних блокових кодів використовуються в багатьох областях застосування, в тому числі й додатках. Наприклад, властивість унікальності синдрому-лінійки лінійних блокових кодів використовується у формуванні решітки, одному з найвідоміших кодів формування. Ця ж властивість використовується в сенсорних мережах для розподіленого кодування джерела.

Згорткові коди

Додаткові відомості: Згорткове кодування

Ідея згорткового коду полягає в тому, щоб кожен символ кодового слова був зваженою сумою різних символів вхідного повідомлення. Це схоже на згортку, яка використовується у лінійних інваріантних до часу системах, для пошуку вихідних даних системи, коли відомі вхідні та імпульсні характеристики.

Отже, як правило, знаходимо вихідні дані системного згорткового кодера, який є згорткою вхідного біта, всупереч положенню згорткового кодера, реєстру.

Фундаментально, згорткові коди пропонують більш високий рівень захисту від шуму, ніж еквівалентний блок коду. У багатьох випадках, вони зазвичай пропонують велику простоту реалізації над блоком коду рівної потужності. Кодер, як правило, проста схема, яка має стан пам'яті і якась логіка зворотного зв'язку, як правило, XOR-шлюзу. Декодер може бути реалізований в програмному забезпеченні або в прошивці.

Алгоритм Вітербі є оптимальним алгоритмом, який використовується для декодування згорткових кодів. Є спрощення, щоб знизити обчислювальне навантаження, воно полягає у пошуку лише найбільш вірогідних шляхів. Незважаючи на те, що такі спрощення не є оптимальними, завдяки їхньому застосуванню є хороші результати в умовах низького рівня шуму.

Згорткові коди використовуються в модемах голосового зв'язку (V.32, V.17, V.34) та в GSM мобільних телефонів, а також супутникових і військових пристроях зв'язку^:26.

Криптографічне кодування

Криптографія або криптографічне кодування має практичне застосування і займається вивченням методів для безпечного спілкування в присутності третіх осіб, так званих супротивників. У більш загальному сенсі, йдеться про побудову і аналіз протоколів, що блокують діяльність супротивників, різні аспекти безпеки інформації, такі як конфіденційність, цілісність, автентифікація та невідмовність, що є головним для сучасної криптографії та інформаційної безпеки. Сучасна криптографія тісно пов'язана із дисциплінами: математика, інформатика та електротехніка. До застосувань криптографії належать банкомати, комп'ютерні паролі та електронна комерція.

Криптографія до теперішнього часу була фактично синонімом шифрування, перетворенням інформації з читабельного стану в очевидну нісенітницю. Так, наприклад, автор зашифрованого повідомлення поділився технікою декодування, необхідною для відновлення вихідної інформації, лише із передбачуваними одержувачами, тим самим завадивши небажаним особам робити те саме. З часів Першої світової війни і появою комп'ютерів методи, використовувані для виконання криптології стають все більш складними, а їх застосування — все більш поширеним.

Сучасна криптографія в значній мірі ґрунтується на математичній теорії і практиці інформатики; криптографічні алгоритми розроблені навколо припущень обчислювальної твердості, що ускладнює порушення таких алгоритмів на практиці будь-яким супротивником. Теоретично можливо зламати таку систему, але це неможливо зробити будь-якими відомими практичними засобами. Ці схеми тому називаються обчислювально безпечними; теоретичні досягнення, наприклад, вдосконалення цілочисельних алгоритмів факторизації і більш швидкі обчислювальні технології вимагають постійного адаптування цих рішень. Звісно ж існують теоретично безпечні інформаційно-захищені схеми, які, очевидно, неможливо зламати навіть при необмеженій обчислювальній потужності — прикладом є одноразовий блокнот, але ці схеми складніше реалізувати, ніж найбільш теоретично порушувані, але все ж обчислювально безпечні механізми.

З точки зору теорії кодування блокове симетричне шифрування — це кодування блоку вхідного повідомлення M за допомогою, як правило, ненадлишкового коду, обраного з множини можливих відповідно до значення ключа шифрування. У свою чергу обчислення коду автентифікації повідомлень або електронного цифрового підпису є кодуванням блоку вхідного повідомлення M за допомогою надлишкового коду, обраного з множини можливих відповідно до значення ключа.

Лінійне кодування

Лінійний код (або цифрова модуляція смуги частот, або цифровий спосіб передачі базової смуги) — це код, обраний для використання в системі зв'язку з метою передачі основної смуги частот. Лінійне кодування часто використовується для цифрової передачі даних.

Лінійне кодування є цифровим сигналом, який буде передаватися за допомогою дискретної частотно-часової послідовності сигналу, який є оптимально налаштованим для конкретних властивостей фізичного каналу (і приймальних пристроїв). Схема хвильова форма напруги або струму, який використовується для представлення 1 і 0 цифрових даних по лінії передачі називається кодуванням лінії. Поширеними типами кодування ліній є однополярне, полярне, біполярне та манчестерське кодування.

В електроніці, акустиці і суміжних областях науки, хвильова форма сигналу є формою його графіка в залежності від функції часу, незалежно від її величини часу і магнітудної шкали, а також від будь-якого зсуву в часі.

Інші застосування теорії кодування

Іншим завданням теорії кодування є розробка кодів, які допомагають синхронізації. Код може бути спроектований таким чином, щоб зсув фази можна було легко виявити і виправити, а також, щоб кілька сигналів могли надсилатися по одному каналу.

Крім того: застосування кодів, що використовується в деяких системах мобільного зв'язку, є множинним доступом з кодовим поділом каналів (англ. code-division multiple access, CDMA). Кожному телефону присвоюється кодова послідовність, яка випадково некорельована з кодами інших телефонів. Під час передачі, кодове слово використовується для модуляції бітів даних, що є голосовим повідомленням. В свою чергу у приймачі виконується процес демодуляції для відновлення вхідних даних. Властивості цього класу кодів дозволяє багатьом користувачам (з різними кодами), використовувати одночасно один і той же радіоканал. Для приймача, сигнали інших користувачів будуть з'являтися на демодуляторі тільки як сторонній шум низького рівня.

Ще один загальний клас кодів — це автоматичний повторний запит (англ. Automatic repeat request, ARQ) коду. У цих кодах відправник додає надлишок інформації кожного повідомлення (електронного листа) для перевірки помилок, як правило, шляхом додавання контрольних бітів. Якщо контрольні біти не узгоджуються з рештою повідомлення, коли воно надходить, одержувач попросить відправника повторно передати повідомлення. Усі мережеві протоколи, крім найпростіших, глобальної мережі (англ. Wide Area Network, WAN) використовують автоматичний повторний запит. Загальні протоколи включають SDLC, TCP (протокол керування передачею), міжнародне сімейство протоколів X.25 і багато інших.

Групове тестування

Групове тестування використовує коди по-іншому. Наприклад, у великій групі однакових зовні елементів, внутрішні якості візуально не розрізнені (дефектні вироби чи заражені зразки, представлені до тестових досліджень). Ідея групового тестування полягає у тому, щоб визначити, які елементи є «несхожими», використовуючи якомога менше тестів. Походження цієї проблеми — ще за часів Другої світової війни, коли ВПС США потребували перевірки своїх солдатів на сифіліс. Вперше вивчене Робертом Дорфманом у 1943 році, групове тестування — це відносно нова область прикладної математики, яка може бути застосована до широкого кола практичних застосувань і є активною сферою досліджень сьогодні.

Аналогове кодування

Інформація кодується аналогічно і в нейронних мережах мозку, і в аналоговій обробці сигналів та аналоговій електроніці. Аспекти аналогового кодування включають в себе аналогову корекцію помилок, стиснення аналогових даних і аналогове шифрування^:46.

Нейронне кодування

Нейронне кодування є полем нейробіології, пов'язаним з тим, як представлена сенсорна та інша інформація в головному мозку у мережі нейронів. Основною метою вивчення нейронного кодування є: охарактеризувати відносини між подразником та реакцією нейронів індивіда, та окремими або ансамблевими нейронними відповідями, а також — взаємозв'язки між електричною активністю нейронів в ансамблі. Вважається, що нейрони можуть кодувати цифрову і аналогову інформацію, і що нейрони слідують принципам теорії інформації та її стиснення, і виявлення та виправлення помилок в сигналах, які надсилаються по всьому мозку і ширше нервової системи.

Дивиться також

• Посилення кодування
• Покриття коду
• Попередня корекція помилок
• Групове тестування
• Відстань Геммінга, вага Геммінга
• Теорія інформації
• Відстань Лі

Посилання

• Елвін Берлекемп (2014), Алгебраїчна теорія кодування, World Scientific Publishing (переглянуте видання), ISBN 978-9-81463-589-9.
• МакКей Девід. Теорія інформації, виведення, та алгоритмів навчання [Архівовано 17 лютого 2016 у Wayback Machine.] Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
• Віра Плесс (1982), Введення в теорію кодів, що виправляють помилки, John Wiley & Sons, Inc., ISBN 0-471-08684-3.
• Ренді Ятс, Теорія кодування Підручник.