Из Википедии, бесплатной энциклопедии
  (Перенаправлено из кодировки канала )
Перейти к навигации Перейти к поиску
«Перемежитель» перенаправляется сюда. Для оптоволоконного устройства см. Оптический перемежитель .

В вычислительной , телекоммуникационной , теории информации и теории кодирования , в код коррекции ошибок , иногда кода коррекции ошибок ( ECC ) используется для контроля ошибок в данных по ненадежным или зашумленных каналов связи . [1] [2] Основная идея заключается в том, что отправитель кодирует сообщение с избыточной информацией в форме ECC. Избыточность позволяет получателю обнаруживать ограниченное количество ошибок, которые могут возникнуть в любом месте сообщения, и часто исправлять эти ошибки без повторной передачи. Американский математикРичард Хэмминг был пионером в этой области в 1940-х годах и изобрел первый код исправления ошибок в 1950 году: код Хэмминга (7,4) . [2]

ECC отличается от обнаружения ошибок тем, что обнаруженные ошибки можно исправлять, а не просто обнаруживать. Преимущество состоит в том, что системе, использующей ECC, не требуется обратный канал для запроса повторной передачи данных при возникновении ошибки. Обратной стороной является то, что к сообщению добавляются фиксированные накладные расходы, что требует большей полосы пропускания прямого канала. Таким образом, ECC применяется в ситуациях, когда повторные передачи являются дорогостоящими или невозможными, например, при односторонних каналах связи и при многоадресной передаче на несколько приемников . Соединения с длительной задержкой также выигрывают; в случае спутника, вращающегося вокруг Урана , повторная передача из-за ошибок может вызвать задержку в пять часов. Информация ECC обычно добавляется кЗапоминающие устройства большой емкости для восстановления поврежденных данных широко используются в модемах и системах, в которых первичной памятью является память ECC .

Обработка ECC в приемнике может применяться к цифровому потоку битов или при демодуляции несущей с цифровой модуляцией. Для последнего ECC является неотъемлемой частью начального аналого-цифрового преобразования в приемнике. Декодер Витерби реализует алгоритм мягкого решения для демодуляции цифровых данных из аналогового сигнала на фоне шума. Многие кодеры / декодеры ECC также могут генерировать сигнал частоты ошибок по битам (BER), который можно использовать в качестве обратной связи для точной настройки аналоговой принимающей электроники.

Максимальная доля ошибок или пропущенных битов, которые могут быть исправлены, определяется конструкцией кода ECC, поэтому разные коды исправления ошибок подходят для разных условий. Как правило, более сильный код вызывает большую избыточность, которую необходимо передать с использованием доступной полосы пропускания, что снижает эффективную скорость передачи данных при одновременном улучшении принимаемого эффективного отношения сигнал / шум. Кодирования шумным канала теорема о Клода Шеннонаможет использоваться для вычисления максимально достижимой полосы пропускания связи для заданной максимально допустимой вероятности ошибки. Это устанавливает границы теоретической максимальной скорости передачи информации канала с некоторым заданным базовым уровнем шума. Однако это доказательство неконструктивно и, следовательно, не дает представления о том, как создать код, обеспечивающий производительность. После многих лет исследований появились некоторые современные системы ECC [ когда? ] очень близки к теоретическому максимуму.

Прямое исправление ошибок [ править ]

В связи , теории информации и теории кодирования , с прямым исправлением ошибок ( FEC ) или канальное кодирование [3] [4] представляет собой метод , используемый для контроля ошибок в передаче данных по ненадежным или зашумленным каналам связи . Основная идея заключается в том, что отправитель кодирует сообщение избыточным способом, чаще всего с помощью ECC.

Избыточность позволяет получателю обнаруживать ограниченное количество ошибок, которые могут возникнуть в любом месте сообщения, и часто исправлять эти ошибки без повторной передачи. FEC дает приемнику возможность исправлять ошибки без необходимости использования обратного канала для запроса повторной передачи данных, но за счет фиксированной более высокой полосы пропускания прямого канала. Поэтому FEC применяется в ситуациях, когда повторная передача является дорогостоящей или невозможной, например, при односторонних каналах связи и при передаче на несколько приемников в многоадресной передаче . Информация FEC обычно добавляется в устройства массовой памяти (магнитные, оптические и твердотельные / флеш-накопители), чтобы обеспечить восстановление поврежденных данных, широко используется в модемах., используется в системах, где первичной памятью является память ECC, и в широковещательных ситуациях, когда приемник не имеет возможности запрашивать повторную передачу или это может вызвать значительную задержку. Например, в случае спутника, вращающегося вокруг Урана , повторная передача из-за ошибок декодирования может вызвать задержку не менее 5 часов.

Обработка FEC в приемнике может применяться к цифровому битовому потоку или при демодуляции несущей с цифровой модуляцией. Для последнего FEC является неотъемлемой частью начального аналого-цифрового преобразования в приемнике. Декодер Витерби реализует алгоритм мягкого решения для демодуляции цифровых данных из аналогового сигнала на фоне шума. Многие кодеры FEC могут также генерировать сигнал коэффициента ошибок по битам (BER), который можно использовать в качестве обратной связи для точной настройки аналоговой приемной электроники.

Максимальная доля ошибок или недостающих битов, которые могут быть исправлены, определяется конструкцией ECC, поэтому разные коды прямого исправления ошибок подходят для разных условий. Как правило, более сильный код вызывает большую избыточность, которую необходимо передавать с использованием доступной полосы пропускания, что снижает эффективную скорость передачи данных при одновременном улучшении принимаемого эффективного отношения сигнал / шум. Теорема кодирования шумного-каналКлода Шеннона отвечает на вопрос о том, какая полоса пропускания остается для передачи данных при использовании наиболее эффективного кода, который сводит вероятность ошибки декодирования к нулю. Это устанавливает границы теоретической максимальной скорости передачи информации канала с некоторым заданным базовым уровнем шума. Его доказательство неконструктивно и, следовательно, не дает представления о том, как создать код, обеспечивающий производительность. Однако после многих лет исследований некоторые продвинутые системы FEC, такие как полярный код [4], достигают пропускной способности канала Шеннона в рамках гипотезы о кадре бесконечной длины.

Как это работает [ править ]

ECC достигается путем добавления избыточности к передаваемой информации с использованием алгоритма. Избыточный бит может быть сложной функцией многих исходных информационных битов. Исходная информация может появляться или не появляться буквально в закодированном выводе; коды, которые включают немодифицированный ввод в вывод, являются систематическими , тогда как те, которые не включают, являются несистематичными .

Упрощенный пример ECC - это передача каждого бита данных 3 раза, что известно как код повторения (3,1) . Через шумный канал приемник может видеть 8 версий вывода, см. Таблицу ниже.

Триплет получилИнтерпретируется как
0000 (без ошибок)
0010
0100
1000
1111 (без ошибок)
1101
1011
0111

Это позволяет исправить ошибку в любой из трех выборок «большинством голосов» или «демократическим голосованием». Корректирующая способность этого ECC:

  • Ошибка до 1 бита триплета, или
  • пропущено до 2 битов триплета (случаи не указаны в таблице).

Хотя эта тройная модульная избыточность проста в реализации и широко используется, она является относительно неэффективным ECC. Более совершенные коды ECC обычно проверяют несколько последних десятков или даже несколько последних сотен ранее принятых битов, чтобы определить, как декодировать текущую небольшую горстку битов (обычно в группах от 2 до 8 бит).

Усреднение шума для уменьшения количества ошибок [ править ]

Можно сказать, что ECC работает путем «усреднения шума»; поскольку каждый бит данных влияет на многие передаваемые символы, искажение одних символов шумом обычно позволяет извлекать исходные пользовательские данные из других, неповрежденных принятых символов, которые также зависят от тех же пользовательских данных.

  • Из-за этого эффекта «объединения рисков» цифровые системы связи, использующие ECC, как правило, работают значительно выше определенного минимального отношения сигнал / шум, а вовсе не ниже него.
  • Эта тенденция «все или ничего» - эффект обрыва - становится более выраженным по мере использования более сильных кодов, которые ближе подходят к теоретическому пределу Шеннона .
  • Перемежение данных, закодированных с помощью ECC, может уменьшить свойства «все или ничего» передаваемых кодов ECC, когда ошибки канала имеют тенденцию возникать в пакетах. Однако у этого метода есть ограничения; его лучше всего использовать для узкополосных данных.

Большинство систем электросвязи используют код фиксированного канала, рассчитанный на то, чтобы выдерживать ожидаемую частоту ошибок по битам в наихудшем случае , а затем вообще не работают, если частота ошибок по битам становится еще хуже. Однако некоторые системы адаптируются к заданным условиям ошибки канала: некоторые экземпляры гибридного автоматического запроса на повторение используют фиксированный метод ECC, пока ECC может обрабатывать частоту ошибок, а затем переключаются на ARQ, когда частота ошибок становится слишком высокой; адаптивная модуляция и кодирование используют различные скорости ECC, добавляя больше битов исправления ошибок на пакет, когда в канале более высокие частоты ошибок, или удаляя их, когда они не нужны.

Типы ECC [ править ]

Основные статьи: Блочный код и сверточный код
Краткая классификация кодов исправления ошибок

Двумя основными категориями кодов ECC являются блочные коды и сверточные коды .

  • Блочные коды работают с блоками (пакетами) фиксированного размера, состоящими из битов или символов заранее определенного размера. Практические блочные коды обычно могут быть жестко декодированы за полиномиальное время до их длины блока.
  • Сверточные коды работают с битовыми или символьными потоками произвольной длины. Чаще всего они декодируются с помощью алгоритма Витерби , хотя иногда используются и другие алгоритмы. Декодирование Витерби обеспечивает асимптотически оптимальную эффективность декодирования с увеличением длины ограничения сверточного кода, но за счет экспоненциально возрастающей сложности. Завершенный сверточный код также является «блочным кодом» в том смысле, что он кодирует блок входных данных, но размер блока сверточного кода, как правило, произвольный, в то время как блочные коды имеют фиксированный размер, определяемый их алгебраическими характеристиками. Типы завершения для сверточных кодов включают «концевую передачу» и «сброс битов».

Есть много типов блочных кодов; Кодирование Рида-Соломона примечательно тем, что оно широко используется на компакт-дисках , DVD и жестких дисках . К другим примерам классических блочных кодов относятся коды Голея , BCH , многомерная четность и коды Хэмминга .

ECC Хэмминга обычно используется для исправления ошибок флэш- памяти NAND . [5] Это обеспечивает исправление однобитовых ошибок и обнаружение двухбитовых ошибок. Коды Хэмминга подходят только для более надежной одноуровневой ячейки (SLC) NAND. Более плотная многоуровневая ячейка (MLC) NAND может использовать многобитовый корректирующий ECC, такой как BCH или Рида – Соломона. [6] [7] ИЛИ Flash обычно не использует исправление ошибок. [6]

Классические блочные коды обычно декодируются с использованием алгоритмов жесткого решения [8], что означает, что для каждого входного и выходного сигнала принимается жесткое решение, соответствует ли он единице или нулю. Напротив, сверточные коды обычно декодируются с использованием алгоритмов мягкого решения , таких как алгоритмы Витерби, MAP или BCJR , которые обрабатывают (дискретизированные) аналоговые сигналы и которые обеспечивают гораздо более высокую производительность исправления ошибок, чем декодирование с жестким решением.

Почти все классические блочные коды применяют алгебраические свойства конечных полей . Поэтому классические блочные коды часто называют алгебраическими кодами.

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

Большинство кодов прямого исправления ошибок исправляют только перевороты битов, но не вставки или удаления битов. В этой настройке расстояние Хэмминга является подходящим способом измерения частоты ошибок по битам . Несколько кодов прямого исправления ошибок предназначены для исправления вставки и удаления битов, например, коды маркеров и коды водяных знаков. Расстояние Левенштейна - более подходящий способ измерения частоты ошибок по битам при использовании таких кодов.[9]

Кодовая скорость и компромисс между надежностью и скоростью передачи данных [ править ]

См. Также: Скорость передачи данных § Скорость передачи информации

Основным принципом ECC является добавление избыточных битов, чтобы помочь декодеру узнать истинное сообщение, закодированное передатчиком. Кодовая скорость данной системы ЕСС определяется как отношение между количеством информационных битов и общим количеством битов (т. Е. Информацией плюс биты избыточности) в данном коммуникационном пакете. Кодовая скорость, следовательно, является действительным числом. Низкая кодовая скорость, близкая к нулю, подразумевает сильный код, который использует много избыточных битов для достижения хорошей производительности, в то время как большая кодовая скорость, близкая к 1, подразумевает слабый код.

Избыточные биты, защищающие информацию, должны передаваться с использованием тех же коммуникационных ресурсов, которые они пытаются защитить. Это вызывает принципиальный компромисс между надежностью и скоростью передачи данных. [10] В одном крайнем случае, сильный код (с низкой кодовой скоростью) может вызвать значительное увеличение SNR приемника (отношение сигнал / шум), уменьшая частоту ошибок по битам, за счет снижения эффективной скорости передачи данных. . С другой стороны, без использования какого-либо ECC (т. Е. Кодовая скорость, равная 1), используется полный канал для целей передачи информации за счет того, что биты остаются без какой-либо дополнительной защиты.

Один интересный вопрос заключается в следующем: насколько эффективным с точки зрения передачи информации может быть ECC, имеющий незначительную частоту ошибок декодирования? На этот вопрос ответил Клод Шеннон с его второй теоремой, которая гласит, что пропускная способность канала - это максимальная скорость передачи данных, достижимая для любого ECC, частота ошибок которого стремится к нулю: [11] Его доказательство опирается на гауссовское случайное кодирование, которое не подходит для реальные приложения. Верхняя граница, заданная работой Шеннона, вдохновила на долгий путь к разработке ECC, которые могут приблизиться к конечной границе производительности. Различные коды сегодня могут достигать почти предела Шеннона. Однако ECC, обеспечивающие пропускную способность, обычно чрезвычайно сложно реализовать.

Самые популярные ECC имеют компромисс между производительностью и вычислительной сложностью. Обычно их параметры дают диапазон возможных кодовых скоростей, которые можно оптимизировать в зависимости от сценария. Обычно эта оптимизация выполняется для достижения низкой вероятности ошибки декодирования при минимальном влиянии на скорость передачи данных. Другим критерием оптимизации кодовой скорости является уравновешивание низкой частоты ошибок и количества повторных передач с учетом затрат энергии на связь. [12]

Составные коды ECC для повышения производительности [ править ]

Основная статья: Составные коды исправления ошибок

Классические (алгебраические) блочные коды и сверточные коды часто комбинируются в схемах конкатенированного кодирования, в которых сверточный код, декодированный по Витерби с короткой ограниченной длиной, выполняет большую часть работы, а блочный код (обычно Рида-Соломона) с большим размером символа и длиной блока «стирает» любые ошибки, сделанные сверточным декодером. Однопроходное декодирование с помощью этого семейства кодов с исправлением ошибок может дать очень низкий уровень ошибок, но для условий передачи на большие расстояния (например, в глубоком космосе) рекомендуется итеративное декодирование.

Составные коды стали стандартной практикой в ​​спутниковой связи и связи в дальнем космосе с тех пор, как « Вояджер-2» впервые применил эту технику во время встречи с Ураном в 1986 году . Аппарат Galileo использовал итеративные сцепленные коды для компенсации условий очень высокой частоты ошибок, вызванных неисправной антенной.

Проверка четности с низкой плотностью (LDPC) [ править ]

Основная статья: Код проверки на четность с низкой плотностью

Коды с низкой плотностью проверки на четность (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 (см. Исходные коды ).

Турбо-коды [ править ]

Основная статья: Турбо-код

Турбокодирование - это итеративная схема мягкого декодирования, которая объединяет два или более относительно простых сверточных кода и перемежитель для создания блочного кода, который может работать с точностью до доли децибела от предела Шеннона . Предваряя коды 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 - широкополосный доступ , потребительские и бизнес-маркетинговые названия Sprint для 1xEV-DO - Power Vision и Mobile. Широкополосный доступ, соответственно).

Локальная расшифровка и проверка кодов [ править ]

Основные статьи: Локально декодируемый код и Локально тестируемый код

Иногда необходимо декодировать только отдельные биты сообщения или проверить, является ли данный сигнал кодовым словом, и сделать это, не глядя на весь сигнал. Это может иметь смысл в настройке потоковой передачи, где кодовые слова слишком велики, чтобы их можно было классически декодировать достаточно быстро, и где на данный момент интересны только несколько битов сообщения. Также такие коды стали важным инструментом в теории сложности вычислений , например, для разработки вероятностно проверяемых доказательств .

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

Чередование [ править ]

«Перемежитель» перенаправляется сюда. Для оптоволоконного устройства см. Оптический перемежитель .
Краткая иллюстрация идеи чередования

Перемежение часто используется в системах цифровой связи и хранения для повышения производительности кодов прямого исправления ошибок. Многие каналы связи не лишены памяти: ошибки обычно возникают пакетами, а не независимо друг от друга. Если количество ошибок в кодовом слове превышает возможности кода исправления ошибок, ему не удается восстановить исходное кодовое слово. Чередование облегчает эту проблему, перетасовывая исходные символы по нескольким кодовым словам, тем самым создавая более равномерное распределение ошибок. [14] Поэтому перемежение широко используется для исправления пакетных ошибок .

Анализ современных итеративных кодов, как турбо - коды и LDPC - коды , как правило , предполагает независимое распределение ошибок. [15] Поэтому системы, использующие коды LDPC, обычно используют дополнительное перемежение символов в кодовом слове. [16]

Для турбокодов перемежитель является неотъемлемым компонентом, и его правильная конструкция имеет решающее значение для хорошей производительности. [14] [17] Алгоритм итеративного декодирования работает лучше всего, когда в графе факторов , представляющем декодер , нет коротких циклов ; перемежитель выбран, чтобы избежать коротких циклов.

Конструкции перемежителя включают:

  • прямоугольные (или однородные) перемежители (аналогично методу с использованием коэффициентов пропуска, описанному выше)
  • сверточные перемежители
  • случайные перемежители (где перемежитель - известная случайная перестановка)
  • S-случайный перемежитель (где перемежитель - это известная случайная перестановка с ограничением, что никакие входные символы на расстоянии S не появляются на расстоянии S на выходе). [18]
  • бесконкурентный квадратичный многочлен с перестановками (QPP). [19] Примером использования является стандарт мобильной связи 3GPP Long Term Evolution . [20]

В системах связи с множеством несущих перемежение по несущим может использоваться для обеспечения частотного разнесения , например, для уменьшения частотно-избирательного замирания или узкополосных помех. [21]

Пример [ править ]

Передача без чередования :

Сообщение без ошибок: aaaabbbbccccddddeeeeffffggggПередача с пакетной ошибкой: aaaabbbbccc____deeeeffffgggg

Здесь каждая группа одинаковых букв представляет собой 4-битное однобитовое кодовое слово с исправлением ошибок. Кодовое слово cccc изменяется в один бит и может быть исправлено, но кодовое слово dddd изменяется в трех битах, поэтому либо оно не может быть декодировано вообще, либо может быть декодировано неправильно .

С чередованием :

Безошибочные кодовые слова: aaaabbbbccccddddeeeeffffggggС чередованием: abcdefgabcdefgabcdefgabcdefgПередача с пакетной ошибкой: abcdefgabcd____bcdefgabcdefgПолученные кодовые слова после деинтерлейвинга: aa_abbbbccccdddde_eef_ffg_gg

В каждом из кодовых слов «aaaa», «eeee», «ffff» и «gggg» изменяется только один бит, поэтому однобитовый код с исправлением ошибок все декодирует правильно.

Передача без чередования :

Исходное переданное предложение: ThisIsAnExampleOfInterleavingПолучено предложение с пакетной ошибкой: ThisIs______pleOfInterleaving

Термин «пример» в большинстве случаев оказывается непонятным и трудным для исправления.

С чередованием :

Переданное предложение: ThisIsAnExampleOfInterleaving ...Безошибочная передача: TIEpfeaghsxlIrv.iAaenli.snmOten.Получено предложение с пакетной ошибкой: TIEpfe ______ Irv.iAaenli.snmOten.Полученное предложение после деинтерлейвинга: T_isI_AnE_amp_eOfInterle_vin _...

Ни одно слово не потеряно полностью, а недостающие буквы можно восстановить с минимальными догадками.

Недостатки чередования [ править ]

Использование методов чередования увеличивает общую задержку. Это связано с тем, что перед декодированием пакетов должен быть принят весь чередующийся блок. [22] Также перемежители скрывают структуру ошибок; без перемежителя более совершенные алгоритмы декодирования могут воспользоваться структурой ошибок и обеспечить более надежную связь, чем более простой декодер, объединенный с перемежителем [ необходима цитата ] . Пример такого алгоритма основан на структурах нейронной сети [23] .

Программное обеспечение для кодов исправления ошибок [ править ]

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

В этом контексте существует различное доступное программное обеспечение с открытым исходным кодом, перечисленное ниже (не является исчерпывающим).

  • AFF3CT (A Fast Forward Error Correction Toolbox): полная коммуникационная цепочка на C ++ (многие поддерживаемые коды, такие как Turbo, LDPC, полярные коды и т. Д.), Очень быстрая и специализированная на канальном кодировании (может использоваться как программа для моделирования или как библиотека для SDR).
  • IT ++ : библиотека классов и функций C ++ для линейной алгебры, численной оптимизации, обработки сигналов, связи и статистики.
  • OpenAir : реализация (на языке C) спецификаций 3GPP, касающихся Evolved Packet Core Networks.

Список кодов исправления ошибок [ править ]

РасстояниеКод
2 (обнаружение одиночной ошибки)Паритет
3 (исправление одиночных ошибок)Тройное модульное резервирование
3 (исправление одиночных ошибок)совершенный Хэмминга, например Хэмминга (7,4)
4 ( ВТОРОЕ )Расширенный Хэмминга
5 (исправление двойной ошибки)
6 (исправление двойной ошибки / обнаружение тройной ошибки)
7 (исправление трех ошибок)совершенный двоичный код Голея
8 (ТЕКФЕД)расширенный двоичный код Голея
  • Коды AN
  • Код BCH , который может быть разработан для исправления произвольного количества ошибок в каждом блоке кода.
  • Код Бергера
  • Код постоянного веса
  • Сверточный код
  • Коды расширителей
  • Групповые коды
  • Коды Голея , из которых двоичный код Голея представляет практический интерес.
  • Код Гоппа , используемый в криптосистеме Мак-Элиса
  • Код Адамара
  • Код Хагельбаргера
  • Код Хэмминга
  • Код на основе латинского квадрата для небелого шума (преобладающий, например, в широкополосной сети по сравнению с линиями электропередач)
  • Лексикографический код
  • Линейное сетевое кодирование , тип кода с исправлением стирания в сетях вместо двухточечных ссылок
  • Длинный код
  • Код проверки на четность с низкой плотностью , также известный как код Галлагера , как архетип для кодов разреженных графов
  • Код LT , который является почти оптимальным кодом бесскоростной коррекции стирания (код Фонтана)
  • m из n кодов
  • Онлайн-код , почти оптимальный код бесскоростной коррекции стирания
  • Полярный код (теория кодирования)
  • Код Raptor , почти оптимальный код бесскоростной коррекции стирания
  • Исправление ошибок Рида – Соломона
  • Код Рида – Мюллера
  • Повторно-накопительный код
  • Коды повторения , такие как тройное модульное резервирование
  • Спинальный код, бесскоростной нелинейный код, основанный на псевдослучайных хэш-функциях [24]
  • Код Торнадо , почти оптимальный код коррекции стирания и предшественник кодов Фонтана
  • Турбо код
  • Код Уолша-Адамара
  • Циклические проверки избыточности (CRC) могут исправлять 1-битные ошибки для сообщений длиной не более бит для оптимального генератора полиномов степени , см. Математика циклических проверок избыточности # Битовые фильтры

См. Также [ править ]

  • Кодовая скорость
  • Коды стирания
  • Декодер мягкого решения
  • Пакетный код исправления ошибок
  • Обнаружение и исправление ошибок
  • Коды исправления ошибок с обратной связью

Ссылки [ править ]

  1. ^ Гловер, Нил; Дадли, Трент (1990). Практический дизайн коррекции ошибок для инженеров (Версия 1.1, 2-е изд.). Колорадо, США: Cirrus Logic . ISBN 0-927239-00-0. ISBN 978-0-927239-00-4 . 
  2. ^ a b Хэмминг, Ричард Уэсли (апрель 1950 г.). «Коды обнаружения и исправления ошибок». Технический журнал Bell System . США: AT&T . 29 (2): 147–160. DOI : 10.1002 / j.1538-7305.1950.tb00463.x .
  3. ^ Чарльз Ван; Дин Скляр; Дайана Джонсон (зима 2001–2002 гг.). «Кодирование с прямым исправлением ошибок» . Сшивка . Аэрокосмическая корпорация. 3 (1). Архивировано из оригинального 25 февраля 2012 года . Проверено 5 марта 2006 года . Как работают коды прямого исправления ошибок
  4. ^ a b Маундер, Роберт (2016). «Обзор канального кодирования» .
  5. ^ "Коды Хэмминга для устройств флэш-памяти NAND" . EE Times-Asia. По всей видимости, основано на «Техническом примечании Micron TN-29-08: Коды Хэмминга для устройств флэш-памяти NAND» . 2005. Оба говорят: «Алгоритм Хэмминга - это признанный в отрасли метод обнаружения и исправления ошибок во многих приложениях на базе флэш-памяти SLC NAND».
  6. ^ a b «Какие типы ECC следует использовать во флэш-памяти?» (Примечание по применению) . Spansion. 2011. Как алгоритм Рида – Соломона, так и алгоритм BCH являются обычным выбором ECC для MLC NAND flash. ... Блочные коды на основе Хэмминга являются наиболее часто используемыми ECC для SLC .... и Рида – Соломона, и BCH могут обрабатывать множественные ошибки и широко используются во флэш-памяти MLC.
  7. ↑ Джим Кук (август 2007 г.). «Неудобные истины флэш-памяти NAND» (PDF) . п. 28. Для SLC достаточно кода с порогом коррекции 1. t = 4 требуется ... для MLC.
  8. ^ Baldi, M .; Chiaraluce, F. (2008). «Простая схема декодирования распространения убеждений кодов BCH и RS в мультимедийных передачах» . Международный журнал цифрового мультимедийного вещания . 2008 : 1–12. DOI : 10.1155 / 2008/957846 .
  9. ^ Шах, Гаурав; Молина, Андрес; Blaze, Мэтт (2006). «Клавиатуры и скрытые каналы» . USENIX . Проверено 20 декабря 2018 года .
  10. ↑ Це, Давид; Вишванат, Прамод (2005), Основы беспроводной связи , Cambridge University Press , Великобритания
  11. ^ Шеннон, CE (1948). «Математическая теория коммуникации» (PDF) . Технический журнал Bell System . 27 (3–4): 379–423 и 623–656. DOI : 10.1002 / j.1538-7305.1948.tb01338.x .
  12. ^ Rosas, F .; Brante, G .; Соуза, РД; Оберли, К. (2014). «Оптимизация кодовой скорости для достижения энергоэффективной беспроводной связи» . Труды IEEE Wireless Communications and Networking Conference (WCNC) .
  13. ^ Стандарт IEEE, раздел 20.3.11.6 «802.11n-2009» , IEEE, 29 октября 2009 г., по состоянию на 21 марта 2011 г.
  14. ^ a b Vucetic, B .; Юань, Дж. (2000). Турбокоды: принципы и применение . Springer Verlag . ISBN 978-0-7923-7868-6.
  15. ^ Луби, Майкл ; Митценмахер, М .; Shokrollahi, A .; Spielman, D .; Стеманн, В. (1997). «Практические безнадежные коды». Proc. 29-й ежегодный симпозиум Ассоциации вычислительной техники (ACM) по теории вычислений .
  16. ^ «Цифровое видеовещание (DVB); структура кадра второго поколения, системы кодирования каналов и модуляции для вещания, интерактивных услуг, сбора новостей и других приложений спутниковой широкополосной связи (DVB-S2)». En 302 307 . ETSI (V1.2.1). Апрель 2009 г.
  17. ^ Эндрюс, KS; Divsalar, D .; Долинар, С .; Hamkins, J .; Джонс, CR; Поллара, Ф. (ноябрь 2007 г.). «Разработка кодов Turbo и LDPC для приложений дальнего космоса». Труды IEEE . 95 (11): 2142–2156. DOI : 10.1109 / JPROC.2007.905132 .
  18. ^ Dolinar, S .; Дивсалар, Д. (15 августа 1995 г.). «Распределение весов для турбокодов с использованием случайных и неслучайных перестановок». Отчет о ходе реализации ТДА : 42–122. CiteSeerX 10.1.1.105.6640 . 
  19. Перейти ↑ Takeshita, Oscar (2006). "Перемежители полиномов с перестановками: алгебро-геометрическая перспектива". IEEE Transactions по теории информации . 53 (6): 2116–2132. arXiv : cs / 0601048 . DOI : 10.1109 / TIT.2007.896870 .
  20. ^ 3GPP TS 36.212 , версия 8.8.0, стр. 14
  21. ^ "Цифровое видеовещание (DVB); Структура кадра, кодирование каналов и модуляция для системы цифрового наземного телевизионного вещания второго поколения (DVB-T2)". En 302 755 . ETSI (V1.1.1). Сентябрь 2009 г.
  22. ^ Технарь (3 июня 2010). «Объяснение чередования» . Блог W3 Techie . Проверено 3 июня 2010 года .
  23. ^ Крастанов, Стефан; Цзян, Лян (8 сентября 2017 г.). «Вероятностный декодер глубинной нейронной сети для кодов стабилизатора» . Научные отчеты . 7 (1): 1–7. DOI : 10.1038 / s41598-017-11266-1 .
  24. ^ Перри, Джонатан; Балакришнан, Хари; Шах, Деваврат (2011). «Бесчисленные спинномозговые коды» . Материалы 10-го семинара ACM по актуальным темам в сетях . DOI : 10.1145 / 2070562.2070568 . hdl : 1721,1 / 79676 .

Дальнейшее чтение [ править ]

  • МакВильямс, Флоренс Джессим ; Слоан, Нил Джеймс Александр (2007) [1977]. Написано в AT&T Shannon Labs, Флорхэм-Парк, Нью-Джерси, США. Теория кодов, исправляющих ошибки . Математическая библиотека Северной Голландии. 16 (цифровой отпечаток 12-го оттиска, 1-е изд.). Амстердам / Лондон / Нью-Йорк / Токио: Северная Голландия / Elsevier BV . ISBN 0-444-85193-3. LCCN  76-41296 . ISBN 978-0-444-85193-2 .  (xxii + 762 + 6 страниц)
  • Кларк младший, Джордж К .; Каин, Дж. Бибб (1981). Кодирование с коррекцией ошибок для цифровой связи . Нью-Йорк, США: Plenum Press . ISBN 0-306-40615-2. ISBN 978-0-306-40615-7 . 
  • Арази, Бенджамин (1987). Swetman, Herb (ред.). Здравый подход к теории кодов, исправляющих ошибки . Серия MIT Press в компьютерных системах. 10 (1-е изд.). Кембридж, Массачусетс, США / Лондон, Великобритания: Массачусетский технологический институт . ISBN 0-262-01098-4. LCCN  87-21889 . (x + 2 + 208 + 4 страницы)
  • Плетеный, Стивен Б. (1995). Системы контроля ошибок для цифровой связи и хранения . Энглвуд Клиффс, Нью-Джерси, США: Прентис-Холл . ISBN 0-13-200809-2. ISBN 978-0-13-200809-9 . 
  • Уилсон, Стивен Г. (1996). Цифровая модуляция и кодирование . Энглвуд Клиффс, Нью-Джерси, США: Прентис-Холл . ISBN 0-13-210071-1. ISBN 978-0-13-210071-7 . 
  • «Код коррекции ошибок во флеш-памяти NAND с одноуровневой ячейкой» 2007-02-16
  • «Код исправления ошибок во флеш-памяти NAND» 2004-11-29
  • Наблюдения за ошибками, исправлениями и доверием зависимых систем , Джеймс Гамильтон, 26 февраля 2012 г.
  • Сферические упаковки, решетки и группы, Дж. Х. Конвей, Нил Джеймс Александр Слоан, Springer Science & Business Media , 2013-03-09 - Математика - 682 страницы.

Внешние ссылки [ править ]

  • Морелос-Сарагоса, Роберт (2004). "Страница корректирующих кодов (ECC)" . Проверено 5 марта 2006 года .
  • lpdec: библиотека для декодирования LP и связанных вещей (Python)