У сфері обчислювальної техніки, телекомунікацій, теорії інформації та теорії кодування пряма корекція помилок ( FEC ) або канальне кодування є технікою, яка використовується для контролю помилок під час передачі даних через ненадійні або зашумлені канали зв'язку.
Основна ідея полягає в тому, що відправник кодує повідомлення з використанням надлишкової інформації, зазвичай застосовуючи код корекції помилок (*error correction code*, ECC). Завдяки цій надлишковості приймач може не лише виявляти помилки, що можуть виникнути в будь-якій частині повідомлення, але й часто виправляти обмежену кількість цих помилок. Таким чином, зворотний канал для повторного запиту на пересилання може не знадобитися. Вартість такого підходу полягає у збільшенні необхідної пропускної здатності прямого каналу передачі.
Американський математик Річард Геммінг започаткував цей напрям у 1940-х роках і в 1950 році створив перший код для корекції помилок - код Геммінга.
Метод корекції помилок на основі випередження (FEC) застосовується в ситуаціях, коли повторна передача є дорогою або неможливою, наприклад, при односторонніх каналах зв’язку або під час передавання даних до кількох отримувачів у режимі мультикаст.
FEC також корисне для з’єднань з великою затримкою; наприклад, у випадку супутників, що обертаються навколо далеких планет, повторна передача через помилки спричинила б до затримки на кілька годин. Окрім цього метод широко використовується в модемах і стільникових мережах.
Обробка FEC на приймачі може застосовуватися як до цифрового потоку бітів, так і під час демодуляції цифровомодульованого носія. У другому випадку FEC є невід’ємною частиною початкового аналого-цифрового перетворення в приймачі. Декодер Viterbi реалізує алгоритм м’якого рішення для демодуляції цифрових даних з аналогового сигналу, спотвореного шумом. Багато декодерів FEC також можуть генерувати сигнал рівня бітової похибки (BER), який можна використовувати як зворотний зв'язок для точного налаштування аналогової приймальної електроніки.
Інформація FEC додається до пристроїв (магнітних, оптичних і твердотільних/флеш накопичувачів), що дозволяє відновлювати пошкоджені дані. Цей метод також використовується пам'яті комп'ютерів ECC, особливо в системах, де потрібні спеціальні заходи для забезпечення надійності.
Максимальна частка помилок або відсутніх бітів, які можна виправити, визначається конструкцією коду ECC, тому різні коди корекції помилок підходять для різних умов. Загалом, сильніший код вимагає більшої надлишковості, яку необхідно передавати через доступну смугу пропускання, що зменшує ефективну швидкість передачі бітів, водночас підвищуючи співвідношення сигнал/шум на приймальній стороні. Теорема кодування для зашумленого каналу розроблена Клодом Шеноном дозволяє обчислити максимальну досяжну пропускну здатність каналу при заданій максимально допустимій ймовірності помилки. Це встановлює межі теоретично максимальної швидкості передавання інформації через канал із певним базовим рівнем шуму. Однак цей доказ не є конструктивним і, отже, не дає уявлення про те, як створити код що досягне цієї пропускної здатності. Після багатьох років досліджень деякі вдосконалені системи FEC, такі як полярний код наближаються до теоретичного максимуму, визначеного ємністю каналу Шеннона за умови гіпотетичної нескінченної довжини кадру.
Метод Захист від помилок ECC досягається шляхом додавання надлишкових даних до переданої інформації за допомогою спеціального алгоритму. Надлишковий біт може бути складною функцією, що залежить від багатьох бітів оригінальної інформації. Початкова інформація може бути представлена дослівно або в незакодованому результаті: коди, які містять незмінені вхідні дані у виході називаються систематичними, тоді як ті, які не містять, називаються несистематичними.
Простий приклад ECC це передача кожного біта даних тричі, що відомо як код повторення (3,1). при передачі через зашумлений канал приймач може отримати 8 можливих варіантів вихідного сигналу, як показано в табличці нижче: Трійку отримали Інтерпретується як 000 0 (без помилок) 001 0 010 0 100 0 111 1 (без помилок) 110 1 101 1 011 1 Такий метод дозволяє виправити помилку в будь-якому з трьох зразків за допомогою «більшості голосів» або «демократичного голосування». Можливості цього коду ECC такі:
До 1 помилки у будь-якому з трьох бітів у трійці. До 2 відсутніх бітів у трійці (ці випадки не показані в таблиці).
Хоча метод потрійної модульної надлишковості простий в реалізації та широко використовується, потрійна модулярна надмірність є відносно неефективним ECC. Більш ефективніі ECC-коди зазвичай перевіряють останні кілька десятків або навіть останні кілька сотень останніх отриманих бітів, щоб визначити, як декодувати поточну невелику групу бітів (зазвичай у групах від 2 до 8 бітів).
Усереднення шуму для зменшення помилок Метод ECC можна описати як «усереднення шуму»; оскільки кожен біт даних впливає на багато переданих символів, пошкодження деяких символів шумом зазвичай дозволяє витягнути початкові дані користувача з інших, непошкоджених символів, які також залежать від тих самих даних.
Завдяки такому ефекту «розподілу ризику» цифрові комунікаційні системи, що використовують ECC, зазвичай працюють добре при певному мінімальному співвідношенні сигнал/шум, і не працюють зовсім, якщо це співвідношення нижче порогового. Ця тенденція «все або нічого» — так званий ефект обриву — стає більш вираженою, коли використовуються сильніші коди, що наближаються до теоретичної межі Шеннона. Перемежування даних, закодованих за допомогою ECC, може зменшити ефект «все або нічого», коли помилки в каналі мають схильність виникати пакетами. Однак цей метод має обмеження; його найкраще застосовувати для вузькосмугових даних.
Більшість телекомунікаційних систем використовують фіксований код каналу, розроблений для роботи при очікуваному найгіршому показнику бітових помилок, і повністю припиняють функціонування, якщо показник помилок перевищує цей поріг. Однак деякі системи адаптуються до заданих умов помилки каналу: деякі варіанти гібридного автоматичного повторного запиту (ARQ) використовують фіксований метод ECC, поки він може впоратися з рівнем помилок, а потім переходять на ARQ, коли рівень помилок стає занадто високою; Адаптивна модуляція та кодування використовує різні рівні швидкості ECC, додаючи більше коригувальних бітів у пакет при високому рівні помилок у каналі або зменшуючи їх, коли вони не є потрібними.
Типи
Дві основні категорії кодів ECC - це блокові коди та згорткові коди.
Блокові коди працюють із фіксованими блоками (пакетами) бітів або символів попередньо визначеного розміру. Практичні блокові коди, як правило, можна декодувати жорстким методом за поліноміальний час відносно довжини блоку. Згорткові коди працюють із потоками бітів або символів довільної довжини. Найчастіше, для їх декодування використовується алгоритм Вітербі, хоча іноді використовуються й інші алгоритми. Декодування Вітербі забезпечує асимптотично оптимальну ефективність декодування зі збільшенням обмежувальної довжини згорткового коду, однак при цьому складність алгоритму зростає експоненціально. Якщо згортковий код завершується, то він також може розглядатися як «блоковий код», оскільки кодує певний блок вхідних даних. Однак розмір блоку згорткового коду, зазвичай, довільний, тоді як блокові коди мають фіксований розмір, що визначається їх алгебраїчними характеристиками. Прикладами завершення згорткових кодів є «циклічне продовження» та «вимивання бітів».
Існує багато типів блокових кодів; серед них варто відзначити Коди Ріда-Соломона, які широко використовуються в компакт-дисках, DVD-дисках і жорстких дисках. Інші приклади класичних блокових кодів включають коди Голея, BCH-коди, багатовимірні коди парності та коди Хеммінга.
ЕСС-коди Хеммінга часто використовуються для виправлення помилок у NAND-флеш-пам'яті."Hamming codes for NAND flash memory devices" . EE Times-Asia. Apparently based on "Micron Technical Note TN-29-08: Hamming Codes for NAND Flash Memory Devices" . 2005. Both say: "The Hamming algorithm is an industry-accepted method for error detection and correction in many SLC NAND flash-based applications." Цей метод забезпечує виправлення однобітових помилок і виявлення двобітових. Коди Хеммінга підходять лише для більш надійної одношарової комірокової NAND (SLC). У більш щільній багатошаровій комірковій (MLC) NAND можуть застосовуватися багатобітні коригувальні ECC, наприклад BCH або коди Ріда-Соломона. NOR-флеш зазвичай не використовує жодної корекції помилок.
Класичні блокові коди зазвичай декодуються за допомогою жорстко-розв'язувальних алгоритмів, які приймають чітке рішення для кожного вхідного та вихідного сигналу, визначаючи чи відповідає він біту "1" або "0". У свою чергу згорткові коди зазвичай декодуються за допомогою алгоритмів м’якого прийняття рішень, таких як алгоритми Вітербі, MAP або BCJR. Ці алгоритми працюють із (дискретизованими) аналоговими сигналами та забезпечують значно вищу ефективність корекції помилок у порівнянні з жорстко-розв'язуваними алгоритмами.
Майже всі класичні блокові коди використовують алгебраїчні властивості скінченних полів. Через це класичні блокові коди часто називають алгебраїчними кодами.
На відміну від класичних блокових кодів, які часто визначають здатність виявляти або виправляти помилки, багато сучасних блокових кодів, таких як коди LDPC, не мають жодних гарантій. Замість цього сучасні коди оцінюються за рівнем бітових помилок.
Більшість кодів прямого виправлення помилок здатні виправляти лише помилки зміни бітів, але не помилки вставки чи видалення бітів. У цьому контексті відстань Хеммінга є відповідним способом вимірювання рівня бітових помилок. Деякі коди прямого виправлення помилок розроблені для корекції помилок вставки та видалення бітів, наприклад, маркерні коди та водяні знаки-коди. У таких випадках Відстань Левенштейна є більш придатним способом для вимірювання частоти бітових помилок.
Кодова швидкість і компроміс між надійністю та швидкістю передачі даних Основний принцип ECC полягає у додаванні надлишкових бітів, які допомагають декодеру визначити справжнє повідомлення, закодоване передавачем. Кодова швидкість системи ECC визначається як співвідношення між кількістю інформаційних бітів і загальною кількістю бітів (тобто інформаційних плюс надлишкових) у даному пакеті зв’язку. Таким чином, кодова швидкість є дійсним числом. Низька кодова швидкість, близька до нуля, означає сильний код, який використовує багато надлишкових бітів для досягнення високої продуктивності. Натомість висока кодова швидкість, близька до 1, означає слабкий код.
Надлишкові біти, що захищають інформацію, повинні передаватися через ті самі ресурси зв'язку, які вони намагаються захистити. Це призводить до фундаментального компромісу між надійністю та швидкістю передачі даних. В одному з крайніх випадків сильний код (із низькою кодовою швидкістю) може суттєво підвищити співвідношення сигнал/шум (SNR) у приймачі, знижуючи частоту бітових помилок ціною зменшення ефективної швидкості передачі даних. З іншого боку, відсутність ECC (тобто кодова швидкість дорівнює 1) дозволяє повністю використовувати канал для передачі інформації, але залишає біти без додаткового захисту.
Цікавим є питання: наскільки ефективною в плані передачі інформації може бути ECC з незначною ймовірністю декодувальної помилки? На це питання відповів Клод Шеннон своєю другою теоремою, яка стверджує, що пропускна здатність каналу є максимальною швидкістю передачі бітів, досяжною будь-якою ECC із ймовірністю помилки, що прагне до нуля. Його доведення базується на випадковому кодуванні Гауса, яке не є придатним для практичного використання. Однак верхня межа, визначена в роботі Шеннона, надихнула на тривалі дослідження у розробці ECC, які наближаються до граничної продуктивності. Сьогодні існують різні коди здатні майже досягнути межі Шеннона. Однак коди ECC що досягають пропускної здатності зазвичай надзвичайно складні для реалізації.