Схемы контроля ошибок при передаче данных по зашумленным каналам связи

Введение

Схема контроля ошибок в данных при передаче по зашумлённым каналам связи

В вычислительной технике, телекоммуникациях, теории информации и теории кодирования, коррекция ошибок на основе прямого исправления (Forward Error Correction, FEC) или кодирование каналов — это метод, используемый для контроля ошибок при передаче данных по ненадежным или зашумлённым каналам связи. Основная идея заключается в том, что отправитель кодирует сообщение избыточным способом, чаще всего с помощью кода коррекции ошибок (Error Correction Code, ECC). Избыточность позволяет получателю не только обнаруживать ошибки, которые могут возникнуть в любом месте сообщения, но и часто исправлять ограниченное количество ошибок. Таким образом, обратный канал для запроса повторной передачи может не потребоваться. Цена — фиксированная, более высокая пропускная способность канала прямой связи. Американский математик Ричард Хамминг стал пионером в этой области в 1940-х годах и изобрел первый код коррекции ошибок в 1950 году: код Хамминга (7,4). Он обеспечивает коррекцию однобитовых ошибок и обнаружение двухбитовых ошибок. Коды Хамминга подходят только для более надёжных одноуровневых ячеек (SLC) NAND. Для более плотных многоуровневых ячеек (MLC) NAND может использоваться многобитная ECC, исправляющая ошибки, такая как BCH или Reed–Solomon. NOR Flash обычно не использует коррекцию ошибок, что означает, что для каждого входного и выходного сигнала принимается жёсткое решение о том, соответствует ли он биту «1» или «0». В отличие от этого, свёрточные коды обычно декодируются с использованием алгоритмов мягкого решения, таких как алгоритмы Витерби, MAP или BCJR, которые обрабатывают (дискретизированные) аналоговые сигналы и обеспечивают значительно более высокую производительность коррекции ошибок, чем декодирование с жёстким решением. Почти все классические блочные коды применяют алгебраические свойства конечных полей. Поэтому классические блочные коды часто называют алгебраическими кодами. В отличие от классических блочных кодов, которые часто указывают на возможность обнаружения или исправления ошибок, многие современные блочные коды, такие как коды LDPC, не имеют таких гарантий. Вместо этого современные коды оцениваются по их битовой ошибке. Большинство кодов коррекции ошибок исправляют только инверсии битов, но не вставки или удаления битов. В этом случае расстояние Хэмминга является подходящим способом измерения частоты битовых ошибок. Некоторые коды коррекции ошибок предназначены для исправления вставок и удалений битов, такие как коды-маркеры и коды водяных знаков. Расстояние Левенштейна является более подходящим способом измерения частоты битовых ошибок при использовании таких кодов.

In computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels. The central idea is that the sender encodes the message in a redundant way, most often by using an error correction code or error correcting code (ECC). The redundancy allows the receiver not only to detect errors that may occur anywhere in the message, but often to correct a limited number of errors. Therefore a reverse channel to request re transmission may not be needed. The cost is a fixed, higher forward channel bandwidth. The American mathematician Richard Hamming pioneered this field in the 1940s and invented the first error correcting code in 1950: the Hamming (7,4) code. This provides single bit error correction and 2 bit error detection. Hamming codes are only suitable for more reliable single level cell (SLC) NAND. Denser multi level cell (MLC) NAND may use multi bit correcting ECC such as BCH or Reed–Solomon. NOR Flash typically does not use any error correction. which means that for every input and output signal a hard decision is made whether it corresponds to a one or a zero bit. In contrast, convolutional codes are typically decoded using soft decision algorithms like the Viterbi, MAP or BCJR algorithms, which process (discretized) analog signals, and which allow for much higher error correction performance than hard decision decoding. Nearly all classical block codes apply the algebraic properties of finite fields. Hence classical block codes are often referred to as algebraic codes. In contrast to classical block codes that often specify an error detecting or error correcting ability, many modern block codes such as LDPC codes lack such guarantees. Instead, modern codes are evaluated in terms of their bit error rates. Most forward error correction codes correct only bit flips, but not bit insertions or bit deletions. In this setting, the Hamming distance is the appropriate way to measure the bit error rate. A few forward error correction codes are designed to correct bit insertions and bit deletions, such as Marker Codes and Watermark Codes. The Levenshtein distance is a more appropriate way to measure the bit error rate when using such codes.

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

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

The fundamental principle of ECC is to add redundant bits in order to help the decoder to find out the true message that was encoded by the transmitter. The code rate of a given ECC system is defined as the ratio between the number of information bits and the total number of bits (i. e., information plus redundancy bits) in a given communication package. The code rate is hence a real number. A low code rate close to zero implies a strong code that uses many redundant bits to achieve a good performance, while a large code rate close to 1 implies a weak code. The redundant bits that protect the information have to be transferred using the same communication resources that they are trying to protect. This causes a fundamental tradeoff between reliability and data rate. In one extreme, a strong code (with low code rate) can induce an important increase in the receiver SNR (signal to noise ratio) decreasing the bit error rate, at the cost of reducing the effective data rate. On the other extreme, not using any ECC (i. e., a code rate equal to 1) uses the full channel for information transfer purposes, at the cost of leaving the bits without any additional protection. One interesting question is the following: how efficient in terms of information transfer can an ECC be that has a negligible decoding error rate? This question was answered by Claude Shannon with his second theorem, which says that the channel capacity is the maximum bit rate achievable by any ECC whose error rate tends to zero: His proof relies on Gaussian random coding, which is not suitable to real world applications. The upper bound given by Shannon's work inspired a long journey in designing ECCs that can come close to the ultimate performance boundary. Various codes today can attain almost the Shannon limit. However, capacity achieving ECCs are usually extremely complex to implement. The most popular ECCs have a trade off between performance and computational complexity. Usually, their parameters give a range of possible code rates, which can be optimized depending on the scenario. Usually, this optimization is done in order to achieve a low decoding error probability while minimizing the impact to the data rate. Another criterion for optimizing the code rate is to balance low error rate and retransmissions number in order to the energy cost of the communication.

Конкатенные коды ЭКК для повышения производительности

Классические (алгебраические) блочные коды и сверточные коды часто комбинируются в каскадных схемах кодирования, в которых сверточный код с короткой длиной ограничения, декодируемый алгоритмом Витерби, выполняет основную часть работы, а блочный код (обычно код Рида — Соломона) с большим размером символа и длиной блока "устраняет" любые ошибки, допущенные сверточным декодером. Однопроходное декодирование с использованием этого семейства кодов коррекции ошибок может обеспечить очень низкий уровень ошибок, но для условий передачи на большие расстояния (например, в дальнем космосе) рекомендуется итеративное декодирование. Каскадные коды стали стандартной практикой в спутниковой и дальней космической связи с тех пор, как аппарат "Вояджер-2" впервые применил эту технику во время сближения с Ураном в 1986 году. Аппарат "Галилео" использовал итеративные каскадные коды для компенсации очень высокого уровня ошибок, вызванного неисправной антенной.

Коды турбо

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

Недостатки переплетения

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

Программное обеспечение для кодов коррекции ошибок

Моделирование поведения кодов коррекции ошибок (ECC) в программном обеспечении – распространенная практика для разработки, валидации и улучшения ECC. Новый беспроводной стандарт 5G открывает новые возможности применения программных ECC: сети облачного радиодоступа (C-RAN) в контексте программно-определяемого радио (SDR). Идея заключается в непосредственном использовании программных ECC в системах связи. Например, в 5G программные ECC могут быть размещены в облаке, а антенны подключены к этим вычислительным ресурсам, что повышает гибкость сети связи и потенциально увеличивает энергоэффективность системы. В этом контексте существует ряд доступных программных пакетов с открытым исходным кодом, перечисленных ниже (список не является исчерпывающим). AFF3CT (A Fast Forward Error Correction Toolbox): полноценная цепочка связи, реализованная на C++ (поддерживает множество кодов, таких как Turbo, LDPC, Polar и другие), отличается высокой скоростью и специализирована на кодировании каналов (может использоваться как программа для моделирования или как библиотека для SDR). IT++: библиотека классов и функций на C++ для линейной алгебры, численной оптимизации, обработки сигналов, связи и статистики. OpenAir: реализация (на C) спецификаций 3GPP, касающихся развитых сетей пакетной передачи данных.