Обнаружение и исправление ошибок на канальном уровне - Решение и исправление самых разных ошибок на TopOshibok.ru

Data-link layer uses error control techniques to ensure that frames, i.e. bit streams of data, are transmitted from the source to the destination with a certain extent of accuracy.

Errors

When bits are transmitted over the computer network, they are subject to get corrupted due to interference and network problems. The corrupted bits leads to spurious data being received by the destination and are called errors.

Types of Errors

Errors can be of three types, namely single bit errors, multiple bit errors, and burst errors.

Single bit error − In the received frame, only one bit has been corrupted, i.e. either changed from 0 to 1 or from 1 to 0.
Multiple bits error − In the received frame, more than one bits are corrupted.
Burst error − In the received frame, more than one consecutive bits are corrupted.

Error Control

Error control can be done in two ways

Error detection − Error detection involves checking whether any error has occurred or not. The number of error bits and the type of error does not matter.
Error correction − Error correction involves ascertaining the exact number of bits that has been corrupted and the location of the corrupted bits.

For both error detection and error correction, the sender needs to send some additional bits along with the data bits. The receiver performs necessary checks based upon the additional redundant bits. If it finds that the data is free from errors, it removes the redundant bits before passing the message to the upper layers.

Error Detection Techniques

There are three main techniques for detecting errors in frames: Parity Check, Checksum, and Cyclic Redundancy Check (CRC).

Parity Check

The parity check is done by adding an extra bit, called parity bit to the data to make a number of 1s either even in case of even parity or odd in case of odd parity.

While creating a frame, the sender counts the number of 1s in it and adds the parity bit in the following way

In case of even parity: If a number of 1s is even then parity bit value is 0. If the number of 1s is odd then parity bit value is 1.
In case of odd parity: If a number of 1s is odd then parity bit value is 0. If a number of 1s is even then parity bit value is 1.

On receiving a frame, the receiver counts the number of 1s in it. In case of even parity check, if the count of 1s is even, the frame is accepted, otherwise, it is rejected. A similar rule is adopted for odd parity check.

The parity check is suitable for single bit error detection only.

Checksum

In this error detection scheme, the following procedure is applied

Data is divided into fixed sized frames or segments.
The sender adds the segments using 1’s complement arithmetic to get the sum. It then complements the sum to get the checksum and sends it along with the data frames.
The receiver adds the incoming segments along with the checksum using 1’s complement arithmetic to get the sum and then complements it.
If the result is zero, the received frames are accepted; otherwise, they are discarded.

Cyclic Redundancy Check (CRC)

Cyclic Redundancy Check (CRC) involves binary division of the data bits being sent by a predetermined divisor agreed upon by the communicating system. The divisor is generated using polynomials.

Here, the sender performs binary division of the data segment by the divisor. It then appends the remainder called CRC bits to the end of the data segment. This makes the resulting data unit exactly divisible by the divisor.
The receiver divides the incoming data unit by the divisor. If there is no remainder, the data unit is assumed to be correct and is accepted. Otherwise, it is understood that the data is corrupted and is therefore rejected.

Error Correction Techniques

Error correction techniques find out the exact number of bits that have been corrupted and as well as their locations. There are two principle ways

Backward Error Correction (Retransmission) − If the receiver detects an error in the incoming frame, it requests the sender to retransmit the frame. It is a relatively simple technique. But it can be efficiently used only where retransmitting is not expensive as in fiber optics and the time for retransmission is low relative to the requirements of the application.
Forward Error Correction − If the receiver detects some error in the incoming frame, it executes error-correcting code that generates the actual frame. This saves bandwidth required for retransmission. It is inevitable in real-time systems. However, if there are too many errors, the frames need to be retransmitted.

The four main error correction codes are

Hamming Codes
Binary Convolution Code
Reed – Solomon Code
Low-Density Parity-Check Code

Related Articles
Error control in Data Link Layer
Hamming code for single error correction, double error detection
What is the Error Control in the Data Link Layer?
Framing in Data Link Layer
Network Data Link Layer
Design Issues in Data Link Layer
Flow control in Data Link Layer
Data Link Layer Design Issues
The Data Link Layer Frame and Frame Fields
General Data Link Layer Frame Structure
What is Data Link Layer Switching?
What is the data link layer?
What is a Data Link Layer?
Cisco Discovery Protocol(CDP) and Link Layer Dicovery Protocol(LLDP) in Data Link
Feedback-based flow control in data link layer

Kickstart Your Career

Get certified by completing the course

Get Started

Источник

Обнаружение и коррекция ошибок

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

Большая
часть протоколов канального уровня
выполняет только первую задачу —
обнаружение ошибок, считая, что
корректировать ошибки, то есть повторно
передавать данные, содержавшие искаженную
информацию, должны протоколы верхних
уровней. Так работают такие популярные
протоколы локальных сетей, как Ethernet,
Token Ring, FDDI и другие. Однако существуют
протоколы канального уровня, например
LLC2 или LAP-B, которые самостоятельно решают
задачу восстановления искаженных или
потерянных кадров.

Очевидно,
что протоколы должны работать наиболее
эффективно в типичных условиях работы
сети. Поэтому для сетей, в которых
искажения и потери кадров являются
очень редкими событиями, разрабатываются
протоколы типа Ethernet, в которых не
предусматриваются процедуры устранения
ошибок. Действительно, наличие процедур
восстановления данных потребовало бы
от конечных узлов дополнительных
вычислительных затрат, которые в условиях
надежной работы сети являлись бы
избыточными.

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

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

Методы обнаружения ошибок

Все
методы обнаружения ошибок основаны на
передаче в составе кадра данных служебной
избыточной информации, по которой можно
судить с некоторой степенью вероятности
о достоверности принятых данных. Эту
служебную информацию принято называть
контрольной
суммой
(или последовательностью
контроля кадра — Frame Check Sequence, FCS).
Контрольная сумма вычисляется как
функция от основной информации, причем
необязательно только путем суммирования.
Принимающая сторона повторно вычисляет
контрольную сумму кадра по известному
алгоритму и в случае ее совпадения с
контрольной суммой, вычисленной
передающей стороной, делает вывод о
том, что данные были переданы через сеть
корректно. Существует несколько
распространенных алгоритмов вычисления
контрольной суммы, отличающихся
вычислительной сложностью и способностью
обнаруживать ошибки в данных.

Контроль
по паритету
представляет собой наиболее простой
метод контроля данных. В то же время это
наименее мощный алгоритм контроля, так
как с его помощью можно обнаружить
только одиночные ошибки в проверяемых
данных. Метод заключается в суммировании
по модулю 2 всех бит контролируемой
информации. Например, для данных 100101011
результатом контрольного суммирования
будет значение 1. Результат суммирования
также представляет собой один бит
данных, который пересылается вместе с
контролируемой информацией. При искажении
при пересылке любого одного бита исходных
данных (или контрольного разряда)
результат суммирования будет отличаться
от принятого контрольного разряда, что
говорит об ошибке. Однако двойная ошибка,
например 110101010, будет неверно принята
за корректные данные. Поэтому контроль
по паритету применяется к небольшим
порциям данных, как правило, к каждому
байту, что дает коэффициент избыточности
для этого метода 1/8. Метод редко применяется
в вычислительных сетях из-за его большой
избыточности и невысоких диагностических
способностей.

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

Циклический
избыточный контроль (Cyclic Redundancy Check, CRC)
является в настоящее время наиболее
популярным методом контроля в
вычислительных сетях (и не только в
сетях, например, этот метод широко
применяется при записи данных на диски
и дискеты). Метод основан на рассмотрении
исходных данных в виде одного
многоразрядного двоичного числа.
Например, кадр стандарта Ethernet, состоящий
из 1024 байт, будет рассматриваться как
одно число, состоящее из 8192 бит. В качестве
контрольной информации рассматривается
остаток от деления этого числа на
известный делитель R. Обычно в качестве
делителя выбирается семнадцати- или
тридцати трехразрядное число, чтобы
остаток от деления имел длину 16 разрядов
(2 байт) или 32 разряда (4 байт). При получении
кадра данных снова вычисляется остаток
от деления на тот же делитель R, но при
этом к данным кадра добавляется и
содержащаяся в нем контрольная сумма.
Если остаток от деления на R равен нулю,
то делается вывод об отсутствии ошибок
в полученном кадре, в противном случае
кадр считается искаженным.

Этот
метод обладает более высокой вычислительной
сложностью, но его диагностические
возможности гораздо выше, чем у методов
контроля по паритету. Метод CRC обнаруживает
все одиночные ошибки, двойные ошибки и
ошибки в нечетном числе бит. Метод
обладает также невысокой степенью
избыточности. Например, для кадра
Ethernet размером в 1024 байт контрольная
информация длиной в 4 байт составляет
только 0,4 %.

(Существует
несколько модифицированная процедура
вычисления остатка, приводящая к
получению в случае отсутствия ошибок
известного ненулевого остатка, что
является более надежным показателем
корректности.)

Соседние файлы в папке РИС гр.446зс 2015

Источник

Основная задача канального уровня — передача кадров (frame) по каналам связи. На этом уровне и определяется, где в потоке бит начало сообщения, где конец.

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

Дополнительные задачи канального уровня:

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

Работа с кадрами

Физический уровень предназначен для передачи потока бит по КС. А на канальном уровне необходимо передавать не отдельные биты, а целые сообщения. Задача №1 для канального уровня, выделить сообщения из потока бит, которые приходят по среде передачи данных.

Формирование кадра

Например, есть два ноутбука Хост 1 и Хост 2. И на картинке ниже есть три уровня, сетевой, канальный и физический.

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

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

Методы выделения кадров

Чтобы определить, где в потоке бит начинаются и заканчиваются отдельные frame, были придуманы следующие методы:

Указание количества байт;
Вставка байтов (byte stuffing) и битов (bit stuffing);
Средства физического уровня.

Указатель количества байт

Наипростейший способ определить, где начинается и заканчивается кадр — добавлять длину этого кадра в начало кадра. Например, на картинке ниже показано 3 кадра выделенных разным цветом. В начале каждого кадра указано количество байт. Синим цветом — 6, желтым — 8, зеленым — 4.

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

Получатель посчитает, что семь это длина кадра. Далее идет длина следующего кадра. Здесь она два байта, затем длина следующего кадра семь. Если у нас произошла хоть одна ошибка, то будет нарушена последовательность чтений. Следовательно такой метод на практике не годится к применению.

Вставка byte и bit

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

Перед передачей каждого фрейма добавлялись байты DLE STX (start of text), а после окончания передачи фрейма DLE ETX (end of text). Проблема может возникнуть в том, что в данных тоже может встретиться точно такая же последовательность.

Чтобы отличать последовательность, которая встречается в данных от управляющих символов используются Escape последовательности. В протоколе BSC это тоже последовательность символов DLE (data link escape). Если какая-то последовательность управляющих символов встречается в данных перед ними добавляются escape последовательности DLE, чтобы протокол понимал, что в реальности это данные, а не управляющие символы.

Вставка битов применяется в более современных протоколах, таких как HDLC и PPP. Здесь перед началом и концом каждого кадра добавляется последовательность бит состоящая из 01111110. Может возникнуть проблема, если в данных встречаются подряд идущие 6 или более единиц. Чтобы решить эту задачу в данные, после каждых пяти последовательно идущих 1 добавляется 0. Затем, как получатель прочитал 5 последовательно идущих 1 и встретил 0, то он, этот 0 игнорирует.

Средства физического уровня

Другой вид определения начала и конца кадра, это использование средств физического уровня и он применяется в технологии Ethernet. В первом варианте технологии ethernet использовалась преамбула — это последовательность данных, которая передается перед началом каждого кадра. Она состоит из 8 байт. Первые семь байт состоят из чередующихся 0 и 1: 10101010. Последний байт содержит чередующиеся 0 и 1, кроме двух последних бит в котором две единицы. И именно такая последовательность говорит, что начинается новый кадр.

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

Перед отправкой каждого кадра передаются символы J (11000) и K (10001), а после окончания отправки кадра передается символ T (01101).

Обнаружение и исправление ошибок

Самый простой способ это обнаружить ошибку. Например, с помощью контрольной суммы или какого-либо другого алгоритма. Если у нас технология канального уровня использует обнаружение технических ошибок, то кадр в котором произошла ошибка, просто отбрасывается. Попыток восстановить данные не производится.

Более сложный механизм — это исправление ошибок. Чтобы иметь возможность исправить ошибку, нужно добавить к данным дополнительную информацию, с помощью которой мы сможем обнаружить ошибки и восстановить правильные данные. Для этого используются специальные коды исправляющие ошибки.

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

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

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

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

Есть два варианта метода повторной отправки сообщения. Схему которую мы рассмотрели называется с остановкой и ожиданием. Отправитель передает фрейм и останавливается ожидая подтверждение. Следующий кадр передается только после того, как пришло подтверждение о получении предыдущего сообщения. Такой метод используются в технологии канального уровня Wi-Fi.

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

У нас есть несколько вариантов, что можно делать с ошибками. Можно их обнаруживать, исправлять с помощью кодов исправления ошибок, либо с помощью повторной доставки сообщений. Также мы можем исправлять и обнаруживать ошибки на канальном уровне, либо на вышестоящих уровнях.

Множественный доступ к каналам

Как это лучше делать? Практика показала, что на каналах где ошибки возникают редко, например, если данные передаются по проводам, то на канальном уровне лучше использовать простое обнаружение ошибок. А если ошибки в среде передачи данных происходят часто, например как это происходит в wifi? где используются электромагнитное излучение и много помех, то ошибки эффективнее обнаруживать и исправлять прямо на канальном уровне. Модель взаимодействия открытых систем разрабатывалась, когда на практике использовались только каналы связи “точка-точка” — это были последовательные линии связи, которые объединяли большие компьютеры.

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

Подуровни канального уровня

Подуровень №1 — управление логическим каналом (logical link control) LLC, а подуровень №2 — управление доступом к среде (media access control) MAC.

Подуровень LLC отвечает за передачу данных, формирование кадров, обработку ошибок и тому подобное. LLC общий уровень для различных технологий канального уровня.

Подуровень MAC используется, если технология канального уровня с разделяемым доступом. Если технология канального уровня используют соединение “точка-точка”, то подуровень MAC не нужен.

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

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

Услуги подуровня LLC

Мультиплексирование — передача данных через одну технологию канального уровня, нескольких типов протоколов вышестоящего уровня. Управление потоком, если в сети устройства, которые работают с разной скоростью, то более мощное устройство, может начать передавать данные очень быстро, так что более слабые устройства не успевают их принимать. В компьютерных сетях это называется “затопление” и некоторые технологии канального уровня обеспечивают защиту от затопления медленного получателя быстрым отправителем.

Множественный доступ к каналу связи

Предположим, есть какая-то общая среда передачи данных, к которой подключены несколько компьютеров и они начали передавать данные одновременно. Но так как среда передачи данных одна, то данные искажаются и не могут быть прочитаны из среды. Это называется коллизия. Подуровень MAC обеспечивает управление доступом, к разделяемой среде. В один и тот же момент времени, канал связи для передачи данных должен использовать только один отправитель. В противном случае произойдет коллизия и данные искажаются.

Методы управления доступом:

Рандомизированный метод. Предположим, к среде подключено N устройств в этом случае для передачи данных случайным образом выбирается одно из этих устройств с вероятностью 1/N. Такой подход применяется в технологиях канального уровня изернет и вай-фай.
Определение правил использования среды, например, в технологии Token Ring, данные может передавать только одно устройство, у которого сейчас находится токен. После того как это устройство передало данные, оно передает токен следующему устройству и следующее устройство может передавать данные. Хотя такой подход обеспечивает более эффективное использование полосы пропускания канала связи, но он требует более дорогого оборудования. Поэтому на практике получил распространение рандомизированный подход.

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

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

Источник

Обнаруже́ние оши́бок в технике связи — действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) — процедура восстановления информации после чтения её из устройства хранения или канала связи.

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

Содержание

1 Способы борьбы с ошибками
2 Коды обнаружения и исправления ошибок
- 2.1 Блоковые коды
  - 2.1.1 Линейные коды общего вида
    - 2.1.1.1 Минимальное расстояние и корректирующая способность
    - 2.1.1.2 Коды Хемминга
    - 2.1.1.3 Общий метод декодирования линейных кодов
  - 2.1.2 Линейные циклические коды
    - 2.1.2.1 Порождающий (генераторный) полином
    - 2.1.2.2 Коды CRC
    - 2.1.2.3 Коды БЧХ
    - 2.1.2.4 Коды коррекции ошибок Рида — Соломона
  - 2.1.3 Преимущества и недостатки блоковых кодов
- 2.2 Свёрточные коды
  - 2.2.1 Преимущества и недостатки свёрточных кодов
- 2.3 Каскадное кодирование. Итеративное декодирование
- 2.4 Сетевое кодирование
- 2.5 Оценка эффективности кодов
  - 2.5.1 Граница Хемминга и совершенные коды
  - 2.5.2 Энергетический выигрыш
- 2.6 Применение кодов, исправляющих ошибки
3 Автоматический запрос повторной передачи
- 3.1 Запрос ARQ с остановками (stop-and-wait ARQ)
- 3.2 Непрерывный запрос ARQ с возвратом (continuous ARQ with pullback)
- 3.3 Непрерывный запрос ARQ с выборочным повторением (continuous ARQ with selective repeat)
4 См. также
5 Литература
6 Ссылки

Способы борьбы с ошибками[править | править код]

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

В системах связи возможны несколько стратегий борьбы с ошибками:

обнаружение ошибок в блоках данных и автоматический запрос повторной передачи повреждённых блоков — этот подход применяется, в основном, на канальном и транспортном уровнях;
обнаружение ошибок в блоках данных и отбрасывание повреждённых блоков — такой подход иногда применяется в системах потокового мультимедиа, где важна задержка передачи и нет времени на повторную передачу;
исправление ошибок (англ. forward error correction) применяется на физическом уровне.

Коды обнаружения и исправления ошибок[править | править код]

Корректирующие коды — коды, служащие для обнаружения или исправления ошибок, возникающих при передаче информации под влиянием помех, а также при её хранении.

Для этого при записи (передаче) в полезные данные добавляют специальным образом структурированную избыточную информацию (контрольное число), а при чтении (приёме) её используют для того, чтобы обнаружить или исправить ошибки. Естественно, что число ошибок, которое можно исправить, ограничено и зависит от конкретного применяемого кода.

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

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

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

Блоковые коды[править | править код]

Пусть кодируемая информация делится на фрагменты длиной бит, которые преобразуются в кодовые слова длиной бит. Тогда соответствующий блоковый код обычно обозначают $(n,\;k)$ . При этом число $R=\frac{k}{n}$ называется скоростью кода.

Если исходные бит код оставляет неизменными, и добавляет n-k проверочных, такой код называется систематическим, иначе — несистематическим.

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

способность исправлять как можно большее число ошибок,
как можно меньшая избыточность,
простота кодирования и декодирования.

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

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

Линейные коды общего вида[править | править код]

Линейный блоковый код — такой код, что множество его кодовых слов образует -мерное линейное подпространство (назовём его ) в -мерном линейном пространстве, изоморфное пространству -битных векторов.

Это значит, что операция кодирования соответствует умножению исходного -битного вектора на невырожденную матрицу , называемую порождающей матрицей.

Пусть $C^{\perp}$ — ортогональное подпространство по отношению к , а — матрица, задающая базис этого подпространства. Тогда для любого вектора $\overrightarrow{v}\in C$ справедливо:

$\overrightarrow{v}H^T=\overrightarrow{0}.$

Минимальное расстояние и корректирующая способность[править | править код]

Расстоянием Хемминга (метрикой Хемминга) между двумя кодовыми словами $\overrightarrow{u}$ и $\overrightarrow{v}$ называется количество отличных бит на соответствующих позициях:

$d_H(\overrightarrow{u},\;\overrightarrow{v})=\sum_s{|u^{(s)}-v^{(s)}|}$

Минимальное расстояние Хемминга $d_\min=\min_{u\ne v}d_H(\overrightarrow{u},\;\overrightarrow{v})$ является важной характеристикой линейного блокового кода. Она показывает, насколько «далеко» расположены коды друг от друга. Она определяет другую, не менее важную характеристику — корректирующую способность:

$t=\left\lfloor\frac{d_\min-1}{2}\right\rfloor$

Корректирующая способность определяет, сколько ошибок передачи кода (типа $1\leftrightarrow 0$ ) можно гарантированно исправить. То есть вокруг каждого кодового слова имеем -окрестность A_t , которая состоит из всех возможных вариантов передачи кодового слова с числом ошибок ( $1\leftrightarrow 0$ ) не более . Никакие две окрестности двух любых кодовых слов не пересекаются друг с другом, так как расстояние между кодовыми словами (то есть центрами этих окрестностей) всегда больше двух их радиусов $d_H(A,\;B)\geqslant d_\min>2t$ .

Таким образом, получив искажённую кодовую комбинацию из A_t , декодер принимает решение, что исходной была кодовая комбинация , исправляя тем самым не более ошибок.

Поясним на примере. Предположим, что есть два кодовых слова и , расстояние Хемминга между ними равно 3. Если было передано слово , и канал внёс ошибку в одном бите, она может быть исправлена, так как даже в этом случае принятое слово ближе к кодовому слову , чем к любому другому, и, в частности, к . Но если каналом были внесены ошибки в двух битах (в которых отличалось от ), то результат ошибочной передачи окажется ближе к , чем , и декодер примет решение, что передавалось слово .

Коды Хемминга[править | править код]

Коды Хемминга — простейшие линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку. Код Хемминга может быть представлен в таком виде, что синдром

$\overrightarrow{s}=\overrightarrow{r}H^T$

, где $\overrightarrow{r}$

— принятый вектор, будет равен номеру позиции, в которой произошла ошибка. Это свойство позволяет сделать декодирование очень простым.

Общий метод декодирования линейных кодов[править | править код]

Любой код (в том числе нелинейный) можно декодировать с помощью обычной таблицы, где каждому значению принятого слова $\overrightarrow{r}_i$ соответствует наиболее вероятное переданное слово $\overrightarrow{u}_i$ . Однако данный метод требует применения огромных таблиц уже для кодовых слов сравнительно небольшой длины.

Для линейных кодов этот метод можно существенно упростить. При этом для каждого принятого вектора $\overrightarrow{r}_i$ вычисляется синдром $\overrightarrow{s}_i=\overrightarrow{r}_i H^T$ . Поскольку $\overrightarrow{r}_i=\overrightarrow{v}_i+\overrightarrow{e}_i$ , где $\overrightarrow{v}_i$ — кодовое слово, а $\overrightarrow{e}_i$ — вектор ошибки, то $\overrightarrow{s}_i=\overrightarrow{e}_i H^T$ . Затем с помощью таблицы по синдрому определяется вектор ошибки, с помощью которого определяется переданное кодовое слово. При этом таблица получается гораздо меньше, чем при использовании предыдущего метода.

Линейные циклические коды[править | править код]

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

Циклическим кодом является линейный код, обладающий следующим свойством: если $\overrightarrow{v}$ является кодовым словом, то его циклическая перестановка также является кодовым словом.

Слова циклического кода удобно представлять в виде многочленов. Например, кодовое слово $\overrightarrow{v}=(v_0,\;v_1,\;\ldots,\;v_{n-1})$ представляется в виде полинома $v(x)=v_0+v_1 x+\ldots+v_{n-1}x^{n-1}$ . При этом циклический сдвиг кодового слова эквивалентен умножению многочлена на по модулю x^n-1 .

В дальнейшем, если не указано иное, мы будем считать, что циклический код является двоичным, то есть $v_0,\;v_1,\;\ldots$ могут принимать значения 0 или 1.

Порождающий (генераторный) полином[править | править код]

Можно показать, что все кодовые слова конкретного циклического кода кратны определённому порождающему полиному g(x) . Порождающий полином является делителем x^n-1 .

С помощью порождающего полинома осуществляется кодирование циклическим кодом. В частности:

Коды CRC[править | править код]

Коды CRC (англ. cyclic redundancy check — циклическая избыточная проверка) являются систематическими кодами, предназначенными не для исправления ошибок, а для их обнаружения. Они используют способ систематического кодирования, изложенный выше: «контрольная сумма» вычисляется путём деления $x^{n-k}u(x)$ на g(x) . Ввиду того, что исправление ошибок не требуется, проверка правильности передачи может производиться точно так же.

Таким образом, вид полинома g(x) задаёт конкретный код CRC. Примеры наиболее популярных полиномов:

Название кода	Степень	Полином
CRC-12	12	$x^{12}+x^{11}+x^{3}+x^{2}+x+1$
CRC-16	16	$x^{16}+x^{15}+x^{2}+1$
CRC-CCITT	16	$x^{16}+x^{12}+x^{5}+1$
CRC-32	32	$x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^{8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1$

Коды БЧХ[править | править код]

Коды Боуза — Чоудхури — Хоквингема (БЧХ) являются подклассом циклических кодов. Их отличительное свойство — возможность построения кода БЧХ с минимальным расстоянием не меньше заданного. Это важно, потому что, вообще говоря, определение минимального расстояния кода есть очень сложная задача.

Коды коррекции ошибок Рида — Соломона[править | править код]

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

Математически коды Рида — Соломона являются кодами БЧХ.

Преимущества и недостатки блоковых кодов[править | править код]

Хотя блоковые коды, как правило, хорошо справляются с редкими, но большими пачками ошибок, их эффективность при частых, но небольших ошибках (например, в канале с АБГШ), менее высока.

Свёрточные коды[править | править код]

Свёрточный кодер ( $k=7,\;R=1/2$ )

Свёрточные коды, в отличие от блоковых, не делят информацию на фрагменты и работают с ней как со сплошным потоком данных.

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

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

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

Преимущества и недостатки свёрточных кодов[править | править код]

Свёрточные коды эффективно работают в канале с белым шумом, но плохо справляются с пакетами ошибок. Более того, если декодер ошибается, на его выходе всегда возникает пакет ошибок.

Каскадное кодирование. Итеративное декодирование[править | править код]

Преимущества разных способов кодирования можно объединить, применив каскадное кодирование. При этом информация сначала кодируется одним кодом, а затем другим, в результате получается код-произведение.

Например, популярной является следующая конструкция: данные кодируются кодом Рида-Соломона, затем перемежаются (при этом символы, расположенные близко, помещаются далеко друг от друга) и кодируются свёрточным кодом. На приёмнике сначала декодируется свёрточный код, затем осуществляется обратное перемежение (при этом пачки ошибок на выходе свёрточного декодера попадают в разные кодовые слова кода Рида — Соломона), и затем осуществляется декодирование кода Рида — Соломона.

Некоторые коды-произведения специально сконструированы для итеративного декодирования, при котором декодирование осуществляется в несколько проходов, каждый из которых использует информацию от предыдущего. Это позволяет добиться большой эффективности, однако декодирование требует больших ресурсов. К таким кодам относят турбо-коды и LDPC-коды (коды Галлагера).

Сетевое кодирование[править | править код]

Оценка эффективности кодов[править | править код]

Эффективность кодов определяется количеством ошибок, которые тот может исправить, количеством избыточной информации, добавление которой требуется, а также сложностью реализации кодирования и декодирования (как аппаратной, так и в виде программы для ЭВМ).

Граница Хемминга и совершенные коды[править | править код]

Пусть имеется двоичный блоковый (n,k) код с корректирующей способностью . Тогда справедливо неравенство (называемое границей Хемминга):

$\sum_{i=0}^t {n\choose i}\leqslant 2^{n-k}.$

Коды, удовлетворяющие этой границе с равенством, называются совершенными. К совершенным кодам относятся, например, коды Хемминга. Часто применяемые на практике коды с большой корректирующей способностью (такие, как коды Рида — Соломона) не являются совершенными.

Энергетический выигрыш[править | править код]

При передаче информации по каналу связи вероятность ошибки зависит от отношения сигнал/шум на входе демодулятора, таким образом, при постоянном уровне шума решающее значение имеет мощность передатчика. В системах спутниковой и мобильной, а также других типов связи остро стоит вопрос экономии энергии. Кроме того, в определённых системах связи (например, телефонной) неограниченно повышать мощность сигнала не дают технические ограничения.

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

Применение кодов, исправляющих ошибки[править | править код]

Коды, исправляющие ошибки, применяются:

в системах цифровой связи, в том числе: спутниковой, радиорелейной, сотовой, передаче данных по телефонным каналам.
в системах хранения информации, в том числе магнитных и оптических.

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

Автоматический запрос повторной передачи[править | править код]

Системы с автоматическим запросом повторной передачи (ARQ — Automatic Repeat reQuest) основаны на технологии обнаружения ошибок. Распространены следующие методы автоматического запроса:

Запрос ARQ с остановками (stop-and-wait ARQ)[править | править код]

Идея этого метода заключается в том, что передатчик ожидает от приемника подтверждения успешного приема предыдущего блока данных перед тем, как начать передачу следующего. В случае, если блок данных был принят с ошибкой, приемник передает отрицательное подтверждение (negative acknowledgement, NAK), и передатчик повторяет передачу блока. Данный метод подходит для полудуплексного канала связи. Его недостатком является низкая скорость из-за высоких накладных расходов на ожидание.

Непрерывный запрос ARQ с возвратом (continuous ARQ with pullback)[править | править код]

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

Непрерывный запрос ARQ с выборочным повторением (continuous ARQ with selective repeat)[править | править код]

При этом подходе осуществляется передача только ошибочно принятых блоков данных.

См. также[править | править код]

Цифровая связь
Код ответа (Код причины завершения)
Линейный код
Циклический код
Код Боуза — Чоудхури — Хоквингема
Код Рида — Соломона
LDPC
Свёрточный код
Турбо-код

Литература[править | править код]

Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and Practice of Error Control Codes. — М.: Мир, 1986. — 576 с.
Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Радио и связь, 1979.
Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. В. Б. Афанасьева. — М.: Техносфера, 2006. — 320 с. — (Мир связи). — 2000 экз. — ISBN 5-94836-035-0.

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

Помехоустойчивое кодирование (11 ноября 2001). — реферат по проблеме кодирования сообщений с исправлением ошибок. Проверено 25 декабря 2006. Архивировано 25 августа 2011 года.
Коды Рида-Соломона. Простой пример. Просто, доступно, на конкретных числах. Для начинающих.

Источник

Обнаружение ошибок в технике связи — действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) — процедура восстановления информации после чтения её из устройства хранения или канала связи.

Способы борьбы с ошибками[]

В системах связи возможны несколько стратегий борьбы с ошибками:

обнаружение ошибок в блоках данных и автоматический запрос повторной передачи повреждённых блоков — этот подход применяется в основном на канальном и транспортном уровнях;
обнаружение ошибок в блоках данных и отбрасывание повреждённых блоков — такой подход иногда применяется в системах потокового мультимедиа, где важна задержка передачи и нет времени на повторную передачу;
исправление ошибок (forward error correction) применяется на физическом уровне.

Коды обнаружения и исправления ошибок[]

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

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

Блоковые коды[]

Пусть кодируемая информация делится на фрагменты длиной $k$ бит, которые преобразуются в кодовые слова длиной $n$ бит. Тогда соответствующий блоковый код обычно обозначают $(n,\;k)$ . При этом число $R={\frac {k}{n}}$ называется скоростью кода.

Если исходные $k$ бит код оставляет неизменными, и добавляет $n-k$ проверочных, такой код называется систематическим, иначе несистематическим.

Задать блоковый код можно по-разному, в том числе таблицей, где каждой совокупности из $k$ информационных бит сопоставляется $n$ бит кодового слова. Однако, хороший код должен удовлетворять, как минимум, следующим критериям:

способность исправлять как можно большее число ошибок,
как можно меньшая избыточность,
простота кодирования и декодирования.

Линейные коды общего вида[]

Линейный блоковый код — такой код, что множество его кодовых слов образует $k$ -мерное линейное подпространство (назовём его $C$ ) в $n$ -мерном линейном пространстве, изоморфное пространству $k$ -битных векторов.

Это значит, что операция кодирования соответствует умножению исходного $k$ -битного вектора на невырожденную матрицу $G$ , называемую порождающей матрицей.

Пусть $C^{\perp }$ — ортогональное подпространство по отношению к $C$ , а $H$ — матрица, задающая базис этого подпространства. Тогда для любого вектора ${\overrightarrow {v}}\in C$ справедливо:

${\overrightarrow {v}}H^{T}={\overrightarrow {0}}.$

Минимальное расстояние и корректирующая способность[]

Основная статья: Расстояние Хемминга

Расстоянием Хемминга (метрикой Хемминга) между двумя кодовыми словами ${\overrightarrow {u}}$ и ${\overrightarrow {v}}$ называется количество отличных бит на соответствующих позициях, $d_{H}({\overrightarrow {u}},\;{\overrightarrow {v}})=\sum _{s}{|u^{(s)}-v^{(s)}|}$ , что равно числу «единиц» в векторе ${\overrightarrow {u}}\oplus {\overrightarrow {v}}$ .

Минимальное расстояние Хемминга $d_{\min }=\min _{u\neq v}d_{H}({\overrightarrow {u}},\;{\overrightarrow {v}})$ является важной характеристикой линейного блокового кода. Она показывает насколько «далеко» расположены коды друг от друга. Она определяет другую, не менее важную характеристику — корректирующую способность:

$t=\left\lfloor {\frac {d_{\min }-1}{2}}\right\rfloor$

, округляем «вниз», так чтобы $2t<d_{\min }$

Корректирующая способность определяет, сколько ошибок передачи кода (типа $1\leftrightarrow 0$ ) можно гарантированно исправить. То есть вокруг каждого кода $A$ имеем $t$ -окрестность $A_{t}$ , которая состоит из всех возможных вариантов передачи кода $A$ с числом ошибок ( $1\leftrightarrow 0$ ) не более $t$ . Никакие две окрестности двух любых кодов не пересекаются друг с другом, так как расстояние между кодами (то есть центрами этих окрестностей) всегда больше двух их радиусов $d_{H}(A,\;B)\geqslant d_{\min }>2t$ .

Таким образом получив искажённый код из $A_{t}$ декодер принимает решение, что был исходный код $A$ , исправляя тем самым не более $t$ ошибок.

Поясним на примере. Предположим, что есть два кодовых слова $A$ и $B$ , расстояние Хемминга между ними равно 3. Если было передано слово $A$ , и канал внёс ошибку в одном бите, она может быть исправлена, так как даже в этом случае принятое слово ближе к кодовому слову $A$ , чем к любому другому, и в частности к $B$ . Но если каналом были внесены ошибки в двух битах (в которых $A$ отличалось от $B$ ) то результат ошибочной передачи $A$ окажется ближе к $B$ , чем $A$ , и декодер примет решение что передавалось слово $B$ .

Коды Хемминга[]

Коды Хемминга — простейшие линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку. Код Хемминга может быть представлен в таком виде, что синдром

${\overrightarrow {s}}={\overrightarrow {r}}H^{T}$

, где ${\overrightarrow {r}}$

Общий метод декодирования линейных кодов[]

Любой код (в том числе нелинейный) можно декодировать с помощью обычной таблицы, где каждому значению принятого слова ${\overrightarrow {r}}_{i}$ соответствует наиболее вероятное переданное слово ${\overrightarrow {u}}_{i}$ . Однако, данный метод требует применения огромных таблиц уже для кодовых слов сравнительно небольшой длины.

Для линейных кодов этот метод можно существенно упростить. При этом для каждого принятого вектора ${\overrightarrow {r}}_{i}$ вычисляется синдром ${\overrightarrow {s}}_{i}={\overrightarrow {r}}_{i}H^{T}$ . Поскольку ${\overrightarrow {r}}_{i}={\overrightarrow {v}}_{i}+{\overrightarrow {e}}_{i}$ , где ${\overrightarrow {v}}_{i}$ — кодовое слово, а ${\overrightarrow {e}}_{i}$ — вектор ошибки, то ${\overrightarrow {s}}_{i}={\overrightarrow {e}}_{i}H^{T}$ . Затем с помощью таблицы по синдрому определяется вектор ошибки, с помощью которого определяется переданное кодовое слово. При этом таблица получается гораздо меньше, чем при использовании предыдущего метода.

Линейные циклические коды[]

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

Циклическим кодом является линейный код, обладающий следующим свойством: если ${\overrightarrow {v}}$ является кодовым словом, то его циклическая перестановка также является кодовым словом.

Слова циклического кода удобно представлять в виде многочленов. Например, кодовое слово ${\overrightarrow {v}}=(v_{0},\;v_{1},\;\ldots ,\;v_{n-1})$ представляется в виде полинома $v(x)=v_{0}+v_{1}x+\ldots +v_{n-1}x^{n-1}$ . При этом циклический сдвиг кодового слова эквивалентен умножению многочлена на $x$ по модулю $x^{n}-1$ .

В дальнейшем, если не указано иное, мы будем считать, что циклический код является двоичным, то есть $v_{0},\;v_{1},\;\ldots$ могут принимать значения 0 или 1.

Порождающий (генераторный) полином[]

Можно показать, что все кодовые слова конкретного циклического кода кратны определённому порождающему полиному $g(x)$ . Порождающий полином является делителем $x^{n}-1$ .

С помощью порождающего полинома осуществляется кодирование циклическим кодом. В частности:

Коды CRC[]

Коды CRC (cyclic redundancy check — циклическая избыточная проверка) являются систематическими кодами, предназначенными не для исправления ошибок, а для их обнаружения. Они используют способ систематического кодирования, изложенный выше: «контрольная сумма» вычисляется путем деления $x^{n-k}u(x)$ на $g(x)$ . Ввиду того, что исправление ошибок не требуется, проверка правильности передачи может производиться точно так же.

Таким образом, вид полинома $g(x)$ задаёт конкретный код CRC. Примеры наиболее популярных полиномов:

название кода	степень	полином
CRC-12	12	$x^{12}+x^{11}+x^{3}+x^{2}+x+1$
CRC-16	16	$x^{16}+x^{15}+x^{2}+1$
CRC-CCITT	16	$x^{16}+x^{12}+x^{5}+1$
CRC-32	32	$x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^{8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1$

Коды БЧХ[]

Коды Боуза — Чоудхури — Хоквингема (БЧХ) являются подклассом циклических кодов. Их отличительное свойство — возможность построения кода БЧХ с минимальным расстоянием не меньше заданного. Это важно, потому что, вообще говоря, определение минимального расстояния кода есть очень сложная задача.

Математически полинома $g(x)$ на множители в поле Галуа.

Коды коррекции ошибок Рида — Соломона[]

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

Математически коды Рида — Соломона являются кодами БЧХ.

Преимущества и недостатки блоковых кодов[]

Свёрточные коды[]

Файл:ECC NASA standard coder.png

Свёрточный кодер ( $k=7,\;R=1/2$ )

Свёрточные коды, в отличие от блоковых, не делят информацию на фрагменты и работают с ней как со сплошным потоком данных.

Преимущества и недостатки свёрточных кодов[]

Каскадное кодирование. Итеративное декодирование[]

Некоторые коды-произведения специально сконструированы для итеративного декодирования, при котором декодирование осуществляется в несколько проходов, каждый из которых использует информацию от предыдущего. Это позволяет добиться большой эффективности, однако, декодирование требует больших ресурсов. К таким кодам относят турбо-коды и LDPC-коды (коды Галлагера).

Оценка эффективности кодов[]

Граница Хемминга и совершенные коды[]

Основная статья: Граница Хэмминга

Пусть имеется двоичный блоковый $(n,k)$ код с корректирующей способностью $t$ . Тогда справедливо неравенство (называемое границей Хемминга):

$\sum _{i=0}^{t}{n \choose i}\leqslant 2^{n-k}.$

Энергетический выигрыш[]

При передаче информации по каналу связи вероятность ошибки зависит от отношения сигнал/шум на входе демодулятора, таким образом при постоянном уровне шума решающее значение имеет мощность передатчика. В системах спутниковой и мобильной, а также других типов связи остро стоит вопрос экономии энергии. Кроме того, в определённых системах связи (например, телефонной) неограниченно повышать мощность сигнала не дают технические ограничения.

Применение кодов, исправляющих ошибки[]

Коды, исправляющие ошибки, применяются:

в системах цифровой связи, в том числе: спутниковой, радиорелейной, сотовой, передаче данных по телефонным каналам.
в системах хранения информации, в том числе магнитных и оптических.

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

Автоматический запрос повторной передачи[]

Запрос ARQ с остановками (stop-and-wait ARQ)[]

Идея этого метода заключается в том, что передатчик ожидает от приемника подтверждения успешного приема предыдущего блока данных перед тем как начать передачу следующего. В случае, если блок данных был принят с ошибкой, приемник передает отрицательное подтверждение (negative acknowledgement, NAK), и передатчик повторяет передачу блока. Данный метод подходит для полудуплексного канала связи. Его недостатком является низкая скорость из-за высоких накладных расходов на ожидание.

Непрерывный запрос ARQ с возвратом (continuous ARQ with pullback)[]

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

Непрерывный запрос ARQ с выборочным повторением (continuous ARQ with selective repeat)[]

При этом подходе осуществляется передача только ошибочно принятых блоков данных.

См. также[]

Цифровая связь
Линейный код
Циклический код
Код Боуза — Чоудхури — Хоквингема
Код Рида — Соломона
LDPC
Свёрточный код
Турбо-код

Литература[]

Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Радио и связь, 1979.
Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986.
Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М.: Техносфера, 2005. — ISBN 5-94836-035-0

Ссылки[]

Имеется викиучебник по теме:
Обнаружение и исправление ошибок

Помехоустойчивое кодирование (11 ноября 2001). — реферат по проблеме кодирования сообщений с исправлением ошибок. Проверено 25 декабря 2006.

Источник