Перейти до вмісту

Код з виправлянням помилок

Матеріал з Вікіпедії — вільної енциклопедії.
(Перенаправлено з Error correction code)

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

Основна ідея полягає в тому, що відправник кодує повідомлення з використанням надлишкової інформації, зазвичай застосовуючи код корекції помилок (*error correction code*, ECC). Завдяки цій надлишковості приймач може не лише виявляти помилки, що можуть виникнути в будь-якій частині повідомлення, але й часто виправляти обмежену кількість цих помилок. Таким чином, зворотний канал для повторного запиту на пересилання може не знадобитися. Вартість такого підходу полягає у збільшенні необхідної пропускної здатності прямого каналу передачі.

Американський математик Річард Геммінг започаткував цей напрям у 1940-х роках і в 1950 році створив перший код для корекції помилок - код Геммінга.[4]

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

FEC також корисне для з’єднань з великою затримкою; наприклад, у випадку супутників, що обертаються навколо далеких планет, повторна передача через помилки спричинила б до затримки на кілька годин. Окрім цього метод широко використовується в модемах і стільникових мережах .

Обробка FEC на приймачі може застосовуватися як до цифрового потоку бітів, так і під час демодуляції цифровомодульованого носія. У другому випадку FEC є невід’ємною частиною початкового аналого-цифрового перетворення в приймачі. Декодер Viterbi реалізує алгоритм м’якого рішення для демодуляції цифрових даних з аналогового сигналу, спотвореного шумом. Багато декодерів FEC також можуть генерувати сигнал рівня бітової похибки (BER), який можна використовувати як зворотний зв'язок для точного налаштування аналогової приймальної електроніки.

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

Максимальна частка помилок або відсутніх бітів, які можна виправити, визначається конструкцією коду ECC, тому різні коди корекції помилок підходять для різних умов. Загалом, сильніший код вимагає більшої надлишковості, яку необхідно передавати через доступну смугу пропускання, що зменшує ефективну швидкість передачі бітів, водночас підвищуючи співвідношення сигнал/шум на приймальній стороні . Теорема кодування для зашумленого каналу розроблена Клодом Шеноном дозволяє обчислити максимальну досяжну пропускну здатність каналу при заданій максимально допустимій ймовірності помилки. Це встановлює межі теоретично максимальної швидкості передавання інформації через канал із певним базовим рівнем шуму. Однак цей доказ не є конструктивним і, отже, не дає уявлення про те, як створити код що досягне цієї пропускної здатності. Після багатьох років досліджень деякі вдосконалені системи FEC, такі як полярний код [3] наближаються до теоретичного максимуму, визначеного ємінстю каналу Шеннона за умови гіпотетичної нескінченної довжини кадру.

Метод

[ред. | ред. код]

Захист від помилок 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-флеш-пам'яті . [5] Цей метод забезпечує виправлення однобітових помилок і виявлення двобітових. Коди Хеммінга підходять лише для більш надійної одношарової комірокової NAND (SLC). У більш щільній багатошаровій комірковій (MLC) NAND можуть застосовуватися багатобітні коригувальні ECC, наприклад BCH або коди Ріда-Соломона. [6] [7] NOR-флеш зазвичай не використовує жодної корекції помилок. [6]

Класичні блокові коди зазвичай декодуються за допомогою жорстко-розв'язувальних алгоритмів[8], які приймають чітке рішення для кожного вхідного та вихідного сигналу, визначаючи чи відповідає він біту "1" або "0". У свою чергу згорткові коди зазвичай декодуються за допомогою алгоритмів м’якого прийняття рішень, таких як алгоритми Вітербі, MAP або BCJR. Ці алгоритми працюють із (дискретизованими) аналоговими сигналами та забезпечують значно вищу ефективність корекції помилок у порівнянні з жорстко-розв'язуваними алгоритмами.

Майже всі класичні блокові коди використовують алгебраїчні властивості скінченних полів . Через це класичні блокові коди часто називають алгебраїчними кодами.

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

Більшість кодів прямого виправлення помилок здатні виправляти лише помилки зміни бітів, але не помилки вставки чи видалення бітів. У цьому контексті відстань Хеммінга є відповідним способом вимірювання рівня бітових помилок . Деякі коди прямого виправлення помилок розроблені для корекції помилок вставки та видалення бітів, наприклад, маркерні коди та водяні знаки-коди. У таких випадках Відстань Левенштейна є більш придатним способом для вимірювання частоти бітових помилок. [9]

Кодова швидкість і компроміс між надійністю та швидкістю передачі даних

[ред. | ред. код]

Основний принцип ECC полягає у додаванні надлишкових бітів, які допомагають декодеру визначити справжнє повідомлення, закодоване передавачем. Кодова швидкість системи ECC визначається як співвідношення між кількістю інформаційних бітів і загальною кількістю бітів (тобто інформаційних плюс надлишкових) у даному пакеті зв’язку. Таким чином, кодова швидкість є дійсним числом. Низька кодова швидкість, близька до нуля, означає сильний код, який використовує багато надлишкових бітів для досягнення високої продуктивності. Натомість висока кодова швидкість, близька до 1, означає слабкий код.

Надлишкові біти, що захищають інформацію, повинні передаватися через ті самі ресурси зв'язку, які вони намагаються захистити. Це призводить до фундаментального компромісу між надійністю та швидкістю передачі даних. [10] В одному з крайніх випадків сильний код (із низькою кодовою швидкістю) може суттєво підвищити співвідношення сигнал/шум (SNR) у приймачі, знижуючи частоту бітових помилок ціною зменшення ефективної швидкості передачі даних. З іншого боку, відсутність ECC (тобто кодова швидкість дорівнює 1) дозволяє повністю використовувати канал для передачі інформації, але залишає біти без додаткового захисту.

Цікавим є питання: наскільки ефективною в плані передачі інформації може бути ECC з незначною ймовірністю декодувальної помилки? На це питання відповів Клод Шеннон своєю другою теоремою, яка стверджує, що пропускна здатність каналу є максимальною швидкістю передачі бітів, досяжною будь-якою ECC із ймовірністю помилки, що прагне до нуля. [11] Його доведення базується на випадковому кодуванні Гауса, яке не є придатним для практичного використання. Однак верхня межа, визначена в роботі Шеннона, надихнула на тривалі дослідження у розробці ECC, які наближаються до граничної продуктивності. Сьогодні існують різні коди здатні майже досягнути межі Шеннона. Однак коди ECC що досягають пропускної здатності зазвичай надзвичайно складні для реалізації.

Найпопулярніші ECC пропонують компроміс між продуктивністю та обчислювальною складністю. Їхні параметри зазвичай дають діапазон можливих кодових швидкостей, які можна оптимізувати залежно від конкретного сценарію. Зазвичай така оптимізація спрямована на досягнення низької ймовірності декодувальної помилки з мінімальним впливом на швидкість передачі даних. Іншим критерієм оптимізації кодової швидкості є баланс між низьким рівнем помилок і кількістю повторних передач для зниження енергетичних витрат на зв’язок. [12]

Об’єднані коди ECC для покращення продуктивності

[ред. | ред. код]
Докладніше: Block code та Convolutional code

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

Каскадні коди стали стандартною практикою в супутниковому та міжпланетному зв’язку з часів, коли апарат «Вояджер-2» вперше використав цю техніку під час свого зближення з Ураном у 1986 році. Космічний апарат Galileo застосовував ітеративні каскадні коди для компенсації дуже високого рівня помилок, спричинені виходом із ладу антени.

Перевірка парності низької щільності (LDPC)

[ред. | ред. код]
Докладніше: Turbo code

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

Коди LDPC були вперше запропоновані Робертом Г. Галлагером у його докторській дисертації в 1960 році. Однак через високу обчислювальну складність реалізації як кодера так і декодера, а також через популярність кодів Ріда-Соломона, вони здебільшого залишалися поза увагою до 1990-х років.

Сьогодні коди LDPC використовуються в багатьох сучасних високошвидкісних стандартах зв’язку, таких як DVB-S2 (цифрове відеомовлення через супутник другого покоління), WiMAX (стандарт IEEE 802.16e для мікрохвильового зв’язку), високошвидкісна бездротова локальна мережа ( IEEE 802.11n) . ), [13] 10GBase-T Ethernet (802.3an) і G.hn/G.9960 (стандарт ITU-T для передачі даних через лінії електропередач, телефонні лінії та коаксіальний кабель). Інші LDPC коди стандартизовані для бездротових стандартів зв’язку в межах 3GPP MBMS (див. fountain codes ).

Турбо коди

[ред. | ред. код]

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

Одним із перших комерційних застосувань турбокодування була цифрова стільникова технологія CDMA2000 1x (TIA IS-2000), розроблена компанією Qualcomm і реалізована операторами Verizon Wireless, Sprint та іншими. Турбокоди також використовуються у вдосконаленій версії CDMA2000 1x спеціально для доступу до Інтернету, 1xEV-DO (TIA IS-856). Як і 1x, технологія EV-DO була розроблена компанією Qualcomm і використовується операторами Verizon Wireless, Sprint та іншими (маркетингова назва Verizon для 1xEV-DO – Broadband Access, маркетингові назви Sprint для споживачів і компаній для 1xEV-DO – Power Vision і Mobile широкосмуговий доступ відповідно).

Локальне декодування та тестування кодів

[ред. | ред. код]

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

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


Не всі локально декодовані коди (LDC) є локально тестованими кодами (LTC) [14] і не всі вони є локально коригувальними кодами (LCC), [15] Наприклад, LCC q-запитами мають експоненційну межу довжини [16] [17] тоді як LDC можуть мати субекспоненціальну довжину. [18] [19]

Перемежування

[ред. | ред. код]
Коротка ілюстрація ідеї чергування

Перемежування широко використовується в системах цифрового зв'язку та зберігання даних для покращення продуктивності кодів прямого виправлення помилок. Багато каналів зв’язку не є безпам’ятними: помилки зазвичай виникають у вигляді сплесків, а не незалежно. Якщо кількість помилок у межах кодового слова перевищує здатність коду виправити помилки, відновити початкове кодове слово не вдається. Перемежування вирішує цю проблему шляхом перетасовування вихідних символів між кількома кодовими словами, тим самим створюючи більш рівномірний розподіл помилок. [20] Тому чергування широко використовується для виправлення сплескових помилок .

Аналіз сучасних ітерованих кодів, таких як турбо-коди та коди LDPC, зазвичай пприпускає незалежний розподіл помилок. [21] Тому системи, які використовують LDPC коди, зазвичай використовують додаткове чергування символів у межах кодового слова. [22]

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

Конструкції перемежувача включають:

  • прямокутні (або рівномірні) перемежувачі (схожі на метод що використовує пропускні фактори, описані вище)
  • згорткові перемежувачі
  • випадкові перемежувачі (де перемежувач є відомою випадковою перестановкою)
  • S-випадковий перемежувач (випадкові перестановки з обмеженням, що жодні вхідні символи, розсташовані не менше ніж на відстані S, не можуть опинитися на такій самій відстані в результаті). [24]
  • квадратичний поліном перестановок без конфліктів (QPP). [25] Приклад використання у стандарті мобільного зв’язку 3GPP Long Term Evolution .

У системах багатоканального зв'язку перемежування між каналами може застосовуватися для забезпечення частотної диверсифікації, наприклад, для зменшення впливу частотно-селективного завмирання або вузькосмугових перешкод. [26]

приклад

[ред. | ред. код]

Передача без чергування : 

Повідомлення без помилок: aaaabbbbccccddddeeeeffffgggg
Передача з пакетною помилкою: aaaabbbbccc____deeeeffffgggg

Тут кожна група однакових літер представляє 4-бітовий код із корекцією однобітових помилок. Кодове слово "cccc" змінене в одному біті та може бути виправлене, але кодове слово "dddd" змінене у трьох бітах, тому або не може бути декодоване взагалі, або може бути декодовано неправильно .

З перемежуванням : 

Кодові слова без помилок: aaaabbbbccccddddeeeeffffgggg
Перемежовується: abcdefgabcdefgabcdefgabcdefg
Передача з пакетною помилкою: abcdefgabcd____bcdefgabcdefg
Отримані кодові слова після деперемежування: aa_abbbbccccdddde_eef_ffg_gg

У кожному з кодових слів « aaaa », « eeee », « ffff » та « gggg » змінено лише один біт, тому код із корекцією однобітових помилок декодує все правильно.

Передача без чергування : 

Оригінальне передане речення: ThisIsAnExampleOfInterleaving
Отримане речення з пакетною помилкою: ThisIs______pleOfInterleaving

Термін « AnExample » стає переважно нерозбірливим і складним для виправлення.

З перемежуванням : 

Передане речення: ThisIsAnExampleOfInterleaving...
Передача без помилок: TIEpfeaghsxlIrv.iAaenli.snmOten.
Отримане речення з пакетною помилкою: TIEpfe______Irv.iAaenli.snmOten.
Отримане речення після деперемежування: T_isI_AnE_amp_eOfInterle_vin_...

Жодне слово не втрачається повністю, і пропущені літери можна відновити з мінімальними припущеннями.

Недоліки чергування

[ред. | ред. код]

Використання технік чергування збільшує загальну затримку. Це пов'язано з тим, що весь блок має бути отриманий перш ніж пакети можуть бути декодовані. [27] Також перемежувачі приховують структуру помилок; без перемежувача більш просунуті алгоритми декодування можуть використовувати структуру помилок для досягнення більш надійної комунікації, ніж простіший декодер у поєднанні з перемежувачем. Прикладом такого алгоритму є структура нейронної мережі [28] .

Моделювання поведінки кодів корекції помилок (ECC) у програмному забезпеченні є поширеною практикою для проєктування, валідації та вдосконалення ECC. Новий стандарт бездротового зв’язку 5G відкриває нові можливості для застосування програмних ECC: це хмарні мережі радіодоступу (C-RAN) у контексті радіо-зв'язку з програмно визначеною архітектурою (SDR) . Ідея полягає в тому, щоб безпосередньо використовувати програмні ECC у комунікаціях. Наприклад, у 5G програмні ECC можуть розташовуватися в хмарі, а антени - підключатися до цих обчислювальних ресурсів підвищуючи таким чином гнучкість комунікаційної мережі та, в перспективі, підвищуючи енергоефективність системи.

У цьому контексті доступні різні Open-source програмні рішення (список неповний):

  • AFF3CT (A Fast Forward Error Correction Toolbox): повний комунікаційний ланцюжок у C++ (підтримує багато кодів, таких як Turbo, LDPC, Polar тощо), дуже швидкий і спеціалізується на канальному кодуванні (може використовуватися як програма для моделювання або як бібліотека для SDR).
  • IT++ : бібліотека C++ класів і функцій для лінійної алгебри, числової оптимізації, обробки сигналів, комунікацій та статистики.
  • OpenAir : реалізація (на С) специфікацій 3GPP, що стосуються еволюційної мережі пакетного ядра.

Список кодів для виправлення помилок

[ред. | ред. код]
Відстань Код
2 (виявлення однієї помилки) Парність
3 (виправлення однієї помилки) Потрійне модульне резервування
3 (виправлення однієї помилки) ідеальний Хеммінг, такий як Хеммінг (7,4)
4 ( SECDED ) Розширений Хеммінг
5 (виправлення подвійної помилки)
6 (виправлення подвійної/потрійної помилки) Код Нордстрома-Робінсона
7 (виправлення трьох помилок) ідеальний двійковий код Голея
8 (TECFED) розширений двійковий код Голея

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

[ред. | ред. код]

Примітки

[ред. | ред. код]
  1. ↑ Charles Wang; Dean Sklar; Diana Johnson (Winter 2001–2002). Forward Error-Correction Coding. Crosslink. The Aerospace Corporation. 3 (1). Архів оригіналу за 14 березня 2012. Процитовано 5 березня 2006.
  2. ↑ Charles Wang; Dean Sklar; Diana Johnson (Winter 2001–2002). Forward Error-Correction Coding. Crosslink. The Aerospace Corporation. 3 (1). Архів оригіналу за 14 березня 2012. Процитовано 5 березня 2006. How Forward Error-Correcting Codes Work]
  3. ↑ а б Maunder, Robert (2016). Overview of Channel Coding.
  4. ↑ Hamming, Richard Wesley (April 1950). Error Detecting and Error Correcting Codes. Bell System Technical Journal. USA: AT&T. 29 (2): 147—160. doi:10.1002/j.1538-7305.1950.tb00463.x. hdl:10945/46756. S2CID 61141773.
  5. ↑ "Hamming codes for NAND flash memory devices" [Архівовано 21 серпня 2016 у Wayback Machine.]. EE Times-Asia. Apparently based on "Micron Technical Note TN-29-08: Hamming Codes for NAND Flash Memory Devices" [Архівовано 29 серпня 2017 у Wayback Machine.]. 2005. Both say: "The Hamming algorithm is an industry-accepted method for error detection and correction in many SLC NAND flash-based applications."
  6. ↑ а б What Types of ECC Should Be Used on Flash Memory? (Application note). Spansion. 2011. Both Reed–Solomon algorithm and BCH algorithm are common ECC choices for MLC NAND flash. ... Hamming based block codes are the most commonly used ECC for SLC.... both Reed–Solomon and BCH are able to handle multiple errors and are widely used on MLC flash.
  7. ↑ Jim Cooke (August 2007). The Inconvenient Truths of NAND Flash Memory (PDF). с. 28. For SLC, a code with a correction threshold of 1 is sufficient. t=4 required ... for MLC.
  8. ↑ A Simple Scheme for Belief Propagation Decoding of BCH and RS Codes in Multimedia Transmissions. International Journal of Digital Multimedia Broadcasting. 2008: 1—12. 2008. doi:10.1155/2008/957846.
  9. ↑ Shah, Gaurav (2006). Keyboards and covert channels. USENIX. Процитовано 20 грудня 2018.
  10. ↑ Tse, David; Viswanath, Pramod (2005), Fundamentals of Wireless Communication, Cambridge University Press, UK
  11. ↑ Shannon, C. E. (1948). A mathematical theory of communication (PDF). Bell System Technical Journal. 27 (3–4): 379–423 & 623–656. doi:10.1002/j.1538-7305.1948.tb01338.x. {{cite journal}}: |hdl-access= вимагає |hdl= (довідка)
  12. ↑ . ISBN 978-1-4799-3083-8. {{cite conference}}: Пропущений або порожній |title= (довідка)
  13. ↑ IEEE Standard, section 20.3.11.6 "802.11n-2009" [Архівовано 3 лютого 2013 у Wayback Machine.], IEEE, 29 October 2009, accessed 21 March 2011.
  14. ↑ Kaufman, Tali; Viderman, Michael. Locally Testable vs. Locally Decodable Codes.
  15. ↑ Brubaker, Ben (9 січня 2024). 'Magical' Error Correction Scheme Proved Inherently Inefficient. Quanta Magazine (англ.). Процитовано 9 січня 2024.
  16. ↑ Kothari, Pravesh K.; Manohar, Peter (2023). An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes. arXiv:2311.00558 [cs.CC].
  17. ↑ Kerenidis, Iordanis; de Wolf, Ronald (9 червня 2003). Exponential lower bound for 2-query locally decodable codes via a quantum argument. Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (англ.). ACM. с. 106–115. arXiv:quant-ph/0208062. doi:10.1145/780542.780560. ISBN 978-1-58113-674-6.
  18. ↑ Yekhanin, Sergey (February 2008). Towards 3-query locally decodable codes of subexponential length. Journal of the ACM (англ.). 55 (1): 1—16. doi:10.1145/1326554.1326555. ISSN 0004-5411.
  19. ↑ Efremenko, Klim (31 травня 2009). 3-query locally decodable codes of subexponential length. Proceedings of the forty-first annual ACM symposium on Theory of computing (англ.). ACM. с. 39—44. doi:10.1145/1536414.1536422. ISBN 978-1-60558-506-2. {{cite book}}: Проігноровано |journal= (довідка)
  20. ↑ а б Vucetic, B.; Yuan, J. (2000). Turbo codes: principles and applications. Springer Verlag. ISBN 978-0-7923-7868-6.
  21. ↑ Practical Loss-Resilient Codes. Proc. 29th Annual Association for Computing Machinery (ACM) Symposium on Theory of Computation. 1997.
  22. ↑ Digital Video Broadcast (DVB); Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other satellite broadband applications (DVB-S2). En 302 307. ETSI (V1.2.1). April 2009.
  23. ↑ Andrews, K. S.; Divsalar, D.; Dolinar, S.; Hamkins, J.; Jones, C. R.; Pollara, F. (November 2007). The Development of Turbo and LDPC Codes for Deep-Space Applications. Proceedings of the IEEE. 95 (11): 2142—2156. doi:10.1109/JPROC.2007.905132.
  24. ↑ Dolinar, S.; Divsalar, D. (15 серпня 1995). Weight Distributions for Turbo Codes Using Random and Nonrandom Permutations. TDA Progress Report. 122: 42—122. Bibcode:1995TDAPR.122...56D. CiteSeerX 10.1.1.105.6640.
  25. ↑ Takeshita, Oscar (2006). Permutation Polynomial Interleavers: An Algebraic-Geometric Perspective. IEEE Transactions on Information Theory. 53 (6): 2116—2132. arXiv:cs/0601048. Bibcode:2006cs........1048T. doi:10.1109/TIT.2007.896870.
  26. ↑ Digital Video Broadcast (DVB); Frame structure, channel coding and modulation for a second generation digital terrestrial television broadcasting system (DVB-T2). En 302 755. ETSI (V1.1.1). September 2009.
  27. ↑ Techie (3 червня 2010). Explaining Interleaving. W3 Techie Blog. Процитовано 3 червня 2010.
  28. ↑ Krastanov, Stefan; Jiang, Liang (8 вересня 2017). Deep Neural Network Probabilistic Decoder for Stabilizer Codes. Scientific Reports. 7 (1): 11003. arXiv:1705.09334. Bibcode:2017NatSR...711003K. doi:10.1038/s41598-017-11266-1. PMC 5591216. PMID 28887480.
  29. ↑ Nordstrom, A.W.; Robinson, J.P. (1967), An optimum nonlinear code, Information and Control, 11 (5–6): 613—616, doi:10.1016/S0019-9958(67)90835-2
  30. ↑ . ISBN 9781450310598. {{cite conference}}: Пропущений або порожній |title= (довідка)

Подальше читання

[ред. | ред. код]

Зовнішні посилання

[ред. | ред. код]
Отримано з https://uk.wikipedia.org/wiki/Код_з_виправлянням_помилок