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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Шрифт Брайля - код, який використовує стиснення даних широко, щоб компенсувати уповільнення часу читання

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

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

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

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

Канальне кодування дає додаткові біти даних, щоб зробити передачу даних стійкішою до збурень у каналі передачі. Звичайний користувач не має уявлення щодо багатьох додатків, які використовують кодування каналу. Типовий музичний компакт-диск використовує код Ріда-Соломона для корекції подряпин і пилу. У цьому додатку каналом передачі є сам CD. Стільникові телефони також користуються методами кодування для корекції завмирання і шуму високої частоти передачі радіосигналу. Модеми даних, телефонні коробки передач і НАСА використовують канальні методи кодування, щоб отримати біти через, наприклад, турбо-код і LDPC коди.

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

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

У 1948 році Клод Шеннон опублікував статтю «Математична теорія зв'язку[ru]» в Bell System Technical Journal. Ця робота присвячена проблемі, як краще кодувати інформацію, яку відправник хоче передати. У цій фундаментальній праці автор використовував інструменти з теорії ймовірностей, розроблених Норбертом Вінером, які перебували в їх стадії зародження і застосовувалися до теорії комунікації в той час. Шеннон розробив інформаційну ентропію як міру невизначеності в повідомленні в той час, однак по суті це було винаходом області теорії інформації. Двійковий код Голея[en] був розроблений в 1949 році. Цей код корекції помилок може виправляти до трьох помилок в кожному з 24-бітного слова і виявляти четверту.

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

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

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

Визначення[ред.ред. код]

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

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

Код є функцією

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

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

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

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

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

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

Властивості[ред.ред. код]

  1. є несингулярною[en], якщо ін'єкційна.
  2. є однозначно декодируємой[en], якщо ін'єкційна.
  3. відбувається миттєвою якщо не є префіксом[en] (і навпаки).

Правило[ред.ред. код]

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

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

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

Приклад[ред.ред. код]

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

Канальне кодування[ред.ред. код]

Мета теорії кодування каналу полягає у тому, щоб знайти коди, які передають швидко, містять багато дійсних кодових слів[en] і можуть виправити або принаймні виявити багато помилок. У той час як не є взаємовиключними, продуктивність в цих областях є компромісом. Таким чином, різні коди є оптимальними для різних областей застосування. Необхідні властивості цього коду в основному залежать від ймовірності помилок, що відбуваються під час передачі. У звичайному компакт-диску, погіршення в основному пил або подряпини. Таким чином, коди використовуються з чергуванням. Дані розкидані по всьому диску.Хоча це і не дуже хороший код, простий код повтору може слугувати зрозумілим прикладом. Припустимо, що ми візьмемо блок бітів даних (що представляє звук) і відправимо його три рази. У приймальнику ми розглянемо три біта повторень за бітом і прийняти більшістю голосів. Поворот на те, що ми не просто посилаємо біти в порядку. Ми чергуємо їх. Блок бітів даних спочатку розділений на 4 менших блоків. Потім ми робимо цикл через блок і відправляємо один біт з першої, то другої і так далі. Це робиться в три рази, щоб розподілити дані по поверхні диска. У контексті простого коду повтору, це не може здатися ефективним. Проте, відомі більш потужні коди, які дуже ефективні при корекції "вибуху" помилки подряпини або плями пилу, коли використовується цей метод перемеження.

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

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

Лінійні коди[ред.ред. код]

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


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

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

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

  • Код довжина слова
  • Загальна кількість дійсних кодових слів
  • Мінімальна відстань між двома дійсними кодовими словами, використовуючи в основному відстань Хеммінга, а іноді і інші відстані, як відстані Лі[en].

Коди лінійних блоків[ред.ред. код]

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

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

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

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

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

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

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

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

Згорткові коди[ред.ред. код]

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

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

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

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

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

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

Криптографія або криптографічне кодування є практикою і вивченням методів для безпечного спілкування[en] в присутності третіх осіб (званих противниками)[4]. У більш загальному сенсі, мова йде про побудову і аналізу протоколів[5] різні аспекти information security такі як даніconfidentiality, data integrity, authentication, and non-repudiation[6], які блокують противників, різні аспекти в області інформаційної безпеки таких як конфіденційність даних, Цілісність інформації, аутентифікації і безвідмовності[en] грають центральну роль в сучасній криптографії. Сучасна криптографія існує на стику дисциплін: математики, інформатики та електротехніки. Застосування криптографії включають в себе Банкомати, комп'ютерні паролі і електронну комерцію.

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

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

Лінійне кодування[ред.ред. код]

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

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

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

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

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

Ще один загальний клас кодів є автоматичний повтор запиту[en] (ARQ) коди. У цих кодах відправник додає надмірність одного електронного листа для перевірки помилок, як правило, шляхом додавання контрольних бітів. Якщо контрольні біти не узгоджуються з іншою частиною повідомлення, коли він прибуває, приймач буде попросити відправника повторно надіслати електронний лист. Все, крім найпростіших мережевих протоколів Wide Area використовувають ARQ. Загальні протоколи включають SDLC (IBM), TCP (Інтернет), X.25 (International) і багато інших. Існує велика область досліджень по цій темі через проблеми узгодження відхиленого пакета проти нового пакету. Чи є новий або це повторна передача? Як правило нумерації використовуються схеми, як в TCP. "RFC793". РЛК. Цільова група Internet Engineering (IETF). Вересень 1981.

Група тестування[ред.ред. код]

Група тестування[en] використовує коди різним способом. Розглянемо велику групу елементів, в яких дуже мало відрізняються певним чином (наприклад, дефектні вироби чи інфікованих випробовуваних). Ідея групового тестування, щоб визначити, які елементи є "різні", використовуючи як кілька тестів, наскільки це можливо. Походження цієї проблеми має своє коріння під час Другої світової війни, коли державам армії ВПС Організації Об'єднаних Націй були необхідні для перевірки своїх солдатів на сифіліс. Вона виникла з новаторського паперу Роберта Дорфмана[en].

Аналогове кодування[ред.ред. код]

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

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

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

Дивиться також[ред.ред. код]

Примітки[ред.ред. код]

  1. Джеймс Ірвін, Девід Харл "Data Communications and Networks". 2002. ст. 18. параграф "2.4.4 Типи кодування". цитата: "Існують чотири типи кодування"
  2. Террас, Аудрій (1999). Аналіз Фур'є на кінцевих груп і додатків. Cambridge University Press. ISBN 0-521-45718-1. 
  3. Блейхута, Річард Е. (2003). Алгебраїчні коди для передачі даних. Cambridge University Press. ISBN 0-521-55374-1. 
  4. Рівест, Рональд Л. (1990). Криптология. У J. Van Leeuwen. Довідник з теоретичної інформатики 1. Elsevier. 
  5. Белларе, Міхір; Рогавей, Філіп (21 September 2005). Введення. Введення в сучасній криптографії. с. 10. 
  6. Менезес, А.Дж; Ван Ошоот, П.С.; Ванстоун, С.А. Довідник з прикладної криптографії. ISBN 0-8493-8523-7. 
  7. Тропп, С.Дж (1990). Spike час прибуття: Високоефективна схема кодування для нейронних мереж. У Екміллер, Р.; Хартманн, Г.; Хауске, Г. Паралельна обробка даних в нейронних системах і комп'ютерах (PDF). Північна Голландія. с. 91–94. ISBN 978-0-444-88390-2. Процитовано 30 June 2013. 
  8. Гедеон, T.; Паркер, A.E.; Дімітров, A.Г. (Весна 2002). Спотворення інформації та нейронного кодування. Канадський журнал прикладної математики 10 (1). с. 10. CiteSeerX: 10.1.1.5.6365. 
  9. Штібер, M. (Липень 2005). Спайк синхронізації точність нейронної корекції помилок: локальна поведінка. Нейронне Обчислення 17 (7). с. 1577–1601. arXiv:q-bio/0501021. doi:10.1162/0899766053723069. 

Посилання[ред.ред. код]