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

У теорії кодування існують чотири основні методи обробки інформаціїДжеймс Ірвін, Девід Харл «Data Communications and Networks» . 2002., ст. 18., параграф «2.4.4 Типи кодування». Цитата: «Існують чотири типи кодування»:

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

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

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

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

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

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

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

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

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

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

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

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

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

Код є функцією (or якщо порожній рядок не є частиною алфавіту).

Де  — це кодове слово, пов'язане з .

Довжина кодового слова записується у вигляді .

Очікувана довжина коду .

Конкатенації кодових слів .

Кодове слово порожнього рядка є самим порожнім рядком:

Властивості є , якщо ін'єкційна. є , якщо ін'єкційна. відбувається миттєвою якщо не є (і навпаки).

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

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

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

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

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

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

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

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

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

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

Алгебраїчна теорія кодування в основному ділиться на два основних типи кодів: Блоки лінійних кодів; Згорткові коди. Вона аналізує наступні три головні властивості коду: довжина кодового слова; загальна кількість дійсних кодових слів; мінімальна відстань між двома дійсними кодовими словами, використовуючи в основному відстань Геммінга, а іноді і інші відстані, як відстані Лі.

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

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

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

Є багато типів лінійних блокових кодів, такі як: Циклічні коди (наприклад, коди Геммінга) Біт парності (наприклад, коди БЧХ (BCH)) Коди Ріда-Соломона

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

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

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

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

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

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

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