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
Основная задача канального уровня — передача кадров (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 и вай-фай.
Мы рассмотрели канальный уровень, его основные задачи. Выяснили, что канальный уровень может обнаруживать и исправлять ошибки. Спасибо за прочтение статьи, надеемся она была для Вас полезной.
Что представляет собой вертикальный и горизонтальный контроль по паритету
8. МЕТОДЫ ПЕРЕДАЧИ ДАННЫХ КАНАЛЬНОГО УРОВНЯ
8.4. Методы обнаружения ошибок
Канальный уровень должен обнаруживать ошибки передачи данных, связанные с искажением бит в принятом кадре данных или с потерей кадра, и по возможности их корректировать.
Большая часть протоколов канального уровня выполняет только первую задачу — обнаружение ошибок, считая, что корректировать ошибки, то есть повторно передавать данные, содержавшие искаженную информацию, должны протоколы верхних уровней. Так работают такие популярные протоколы локальных сетей, как Ethernet , Token Ring , FDDI и другие. Однако существуют протоколы LLC2 или LAP-B самостоятельно решают задачу восстановления искаженных или потерянных кадров.
Однако наличие процедур восстановления данных требует от конечных узлов дополнительных вычислительных затрат, которые в условиях надежной работы сети являются избыточными.
Напротив, если в сети искажения и потери случаются часто, то желательно уже на канальном уровне использовать протокол с коррекцией ошибок, а не оставлять эту работу протоколам верхних уровней.
Поэтому нельзя считать, что один протокол лучше другого потому, что он восстанавливает ошибочные кадры, а другой протокол — нет. Каждый протокол должен работать в тех условиях, для которых он разработан.
Все методы обнаружения ошибок основаны на передаче в составе кадра данных служебной избыточной информации, по которой можно судить о достоверности принятых данных. Эту служебную информации принято называть контрольной суммой (или последовательностью контроля кадра — Frame Check Sequence , PCS). Контрольная сумма вычисляется как функция от основной информации. Принимающая сторона повторно вычисляет контрольную сумму кадра по известному алгоритму и в случае ее совпадения с контрольной суммой, вычисленной передающей стороной, делает вывод о корректости переданных данных.
Существует несколько распространенных алгоритмов вычисления контрольной суммы, отличающихся вычислительной сложностью и способностью обнаруживать ошибки в данных.
Контроль по паритету представляет собой наиболее простой метод контроля данных. В то же время это наименее мощный алгоритм контроля, так как с его помощью можно обнаружить только одиночные ошибки в проверяемых данных. Метод заключается в суммировании по модулю 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 %.
Общие принципы построения сетей. Физический уровень передачи данных. Технологии локальных сетей. Стек протоколов TCP/IP , страница 22
На сегодняшний день коммутация сообщений работает только для некоторых неоперативных служб, причем чаще всего поверх сети с коммутацией пакетов, как служба прикладного уровня.
Лекция 7. Обнаружение и коррекция ошибок. Сжатие данных.
7.1. Способы обнаружения и коррекции ошибок.
При передаче данных неизбежно возникают проблемы искажения и потери информации, что может быть обусловлено как искажениями сигнала в канале, так и ошибками в коммуникационном оборудовании. В общем случае можно рассматривать два вида ошибок: потеря кадра и повреждение кадра. В первом из случаев кадр не доходит до адресата, а во втором полученных кадр содержит несколько ошибочных битов (значение которых изменилось при передаче).
Методы обнаружения и коррекции ошибок включают в себя следующие составляющие:
1. Выявление и исправление ошибок.
2. Положительное подтверждение приема.
3. Повторная передача после истечения времени ожидания
4. Отрицательное подтверждение приема и повторная передача.
Выявление ошибок основано на передаче в составе кадра данных избыточной служебной информации, по которой можно судить с некоторой степенью вероятности о достоверности передаваемых данных. Эту служебную информацию принято называть контрольной суммой.
Контрольная сумма вычисляется как некоторая функция от основной информации. Принимающая сторона повторно вычисляет контрольную сумму и сравнив результат с контрольной суммой в полученном кадре данных делает вывод о корректности принятых данных.
Существует несколько распространенных алгоритмов вычисления контрольной суммы:
1. Контроль по паритету. Представляет собой наименее мощный, но и наиболее простой способ контроля данных. Метод заключается в суммировании по модулю 2 всех бит контролируемой информации. Результат представленный одним битом пересылается вместе с контролируемой информацией. Данный алгоритм позволяет выявить ошибки связанные с искажением в пересылаемых данных одного бита информации. Однако множественная ошибка (при искажении четного числа бит) может быть принята за корректные данные. Контроль по паритету применяется к небольшим порциям данных, как правило к одному байту, что приводит к коэффициенту избыточности равному 1/8.
2. Вертикальный и горизонтальный контроль по паритету. Представляет собой модификацию контроля по паритету. Исходные данные рассматриваются в виде матрицы, строки которой представляют слова (или в частном случае байты) данных. Контрольный разряд отдельно подсчитывается для каждой строки и каждого столбца матрицы. Данный метод позволяет обнаружить большую часть двойных ошибок, однако обладает еще большей, чем контроль по паритету, избыточностью.
3. Циклический избыточный контроль. Метод основан на рассмотрении исходных данных в виде одного многоразрядного двоичного числа. В качестве контрольной информации рассматривается остаток от деления этого числа на заранее известный делитель. Принимающая сторона вновь вычисляет остаток от деления числа, состоящего из контролируемых данных и добавленной к ним в младших разрядах контрольной суммы, на тот же самый делитель. В случае если остаток от деления равен нулю делается вывод об отсутствии ошибок в полученном кадре.
Исправление ошибок реализуется либо при помощи повторной передачи искаженной информации, либо как и в случае выявления ошибок дополнения передаваемых данных служебной информацией. В последнем случае применяется так называемое помехоустойчивое кодирование, позволяющее восстановить искаженную информацию за счет добавления избыточных кодовых комбинаций, которые, при отсутствии ошибок не встречаются в принимаемых данных. Количество ошибок которые возможно исправить, в таком случае, напрямую зависит от количества кодовых комбинаций. Естественно, что помехоустойчивое кодирование, помимо исправления, предоставляет возможность выявления ошибок, в том числе и тех, которые не поддаются исправлению.
Методы обнаружения ошибок
Для обнаружения ошибок применяются методы (техники кодирования), основанные па определении вероятности получения приемником достоверной кодовой комбинации. В качестве такой комбинации может выступать любая протокольная единица данных (PDU, Protocol Data Unit) — блок битов, передаваемый как единое целое и имеющий определенную структуру, включающую как саму передаваемую информацию, так и служебные данные. Служебную информацию принято называть контрольной суммой. Она вычисляется по специальным алгоритмам на основе информационных данных, причем не обязательно в виде суммирования.
Будем считать для определенности, что при передаче протокольных единиц данных контролируются кадры. В этом случае контрольную сумму называют контрольной последовательностью кадра. (FCS, Frame Check Sequence). Передатчик отправляет контрольную последовательность кадра как часть PDU. Приемник на своей стороне вычисляет FCS по известному алгоритму и сравнивает с переданной контрольной последовательностью. Если FCS передатчика и приемника совпадают, то принимается решение, что передача данных по сети выполнена корректно.
Основными методами контроля данных (обнаружения ошибок) являются следующие:
- — контроль по паритету;
- — вертикальный и горизонтальный контроль по паритету;
- — контроль контрольной суммой;
- — контроль циклическим избыточным кодом.
Указанные методы отличаются друг от друга как вычислительной сложностью, так и способностью обнаруживать ошибки.
Контроль по паритету является наиболее простым и в то же время наименее мощным методом контроля. Он предназначен для обнаружения битовых ошибок данных. Его суть заключается в следующем. К информационным данным добавляется один контрольный бит (г = 1), который дополняет количество единичных бит до четного или нечетного значения. В первом случае говорят о контроле четности данных, во втором — о контроле нечетности. Соглашение о выборе вида контроля принимается заранее.
Для обнаружения ошибки все передаваемые биты блока (как информационные, так и контрольный) суммируются по модулю 2. При наличии ошибки в передаваемом блоке (как исходных, так и контрольном) результат суммирования будет отличаться от контрольного разряда, который был принят. Это свидетельствует о наличии ошибки. Однако, если ошибок было четное количество (две, четыре и т.д.), то такое искажение останется незамеченным. Из-за этой особенности данный метод контроля применяется к небольшим блокам данных, обычно байтам. В этом случае избыточность кода составляет 1/8, что является довольно значительным, поэтому в компьютерных сетях контроль но паритету используется редко.
Пример 5.3. Рассмотрим ситуацию нечетного контроля трех информационных бит. В этом случае кодовые слова будут состоять из 4 бит. Разрешенными кодовыми комбинациями будут следующие:
Пробелом отделен контрольный бит. ?
Пример 5.3 иллюстрирует два факта, верных для произвольного количества информационных бит:
- 1. При контроле по паритету только половина кодовых комбинаций оказывается разрешенной (8 кодов из 16 возможных).
- 2. Минимальное расстояние кода dmm = 2, т.е. возможно только обнаруживать битовые ошибки, по нс исправлять их.
Вертикальный и горизонтальный контроль по парит,егпу во многом похож на рассмотренный выше метод с тем отличием, что информационные данные представляются (располагаются) в виде матрицы. Строками этой матрицы являются отдельные байты данных. Контрольные биты данных добавляются как для каждой строки, так и для каждого столбца (рис. 5.1).
Бит паритета «р» (горизонтальный контроль) добавляется к каждому передаваемому символу. Бит паритета вертикального контроля рассчитывается для каждой
Рис. 5.1. Вертикальный и горизонтальный контроль по паритету
позиции бита в символе. Вертикальные контрольные биты собираются в отдельный контрольный символ (байт).
Данный метод позволяет обнаружить большую часть ошибок кратности 2. В то же время он обладает еще большей избыточностью но сравнению с обычным контролем по паритету, поэтому в реальных СПД вертикальный и горизонтальный контроль по паритету почти не применяется.
Контрольная сумма представляет собой дополнительный код (см. пример 3.2) суммы всех байт кодового слова. Суммирование выполняется но модулю разрядности поля контрольного кода. Дополнение суммы происходит до нуля (до следующего за максимально возможным числом разрядной сетки, когда все разряды представляют собой двоичные единицы, например, FF).
Передатчик отправляет информационные данные и контрольную сумму. Прием- пик на своей стороне суммирует все байты или слова кадра,, включая контрольные биты. Суммирование выполняется по тому же модулю (разрядности поля контрольного кода). В результате должно получиться то же число 0 (следующее за FF). Отличие в значении позволяет сделать вывод, что при передаче была допущена ошибка.
Вычисление контрольных сумм является одним из самых простых способов контроля кадров (вероятность определения ошибок достигает 99,9%). При постоянной длине контрольного кода с увеличением количества информационных данных в одной PDU вероятность обнаружения ошибок снижается. Метод контрольных сумм применяется для выявления битовых ошибок.
Рассмотренные три метода обнаружения ошибок являются достаточно простыми как с алгоритмической точки зрения, так и в технической реализации. Однако все они не позволяют обнаружить пакетные ошибки заданной кратности. Для решения этой проблемы может быть применен метод циклического избыточного контроля.
Циклический избыточный контроль (Cyclic Redundancy Check, CRC) является популярным методом обнаружения ошибок в СПД и других задачах, где не требуется исправление пакетных ошибок, например, при записи данных на жесткие и оптические носители.
Суть метода CRC заключается в следующем. На передатчике формируется п-бит- нос кодовое слово, состоящее из к информационных и г проверочных бит (поле FCS). До передачи кадра все проверочные биты имеют значение 0. Кадр целиком (все п бит, включая и обнуленные проверочные) в виде двоичного числа делится за некоторый делитель Р. Остаток от деления по модулю 2 помещается в иоле FCS. На стороне приемника принятый кадр целиком делится на тот же делитель Р. Если остаток от деления на приемнике равен 0, то принимается решение, что ошибок при передаче данных не произошло, иначе данные считаются искаженными.
Число бит в кадре может быть достаточно большим. Например, стандартный кадр Ethernet имеет длину 1024 байт, т.с. число будет содержать 8096 бит.
В циклических кодах передаваемые кадры имеют определенную структуру, т.е. информационные и проверочные биты всегда располагаются на определенных местах. С целью упрощения кодирования и декодирования проверочные биты обычно располагают в конце блока. Каждый блок данных кодируется и декодируется независимо от других блоков.
При практической реализации CRC значения бит представляются в виде многочленов от некоторой фиксированной переменной х. Коэффициентами многочленов являются двоичные числа, которые соответствуют передаваемым битам. Например, блок данных 10011010 представляется в виде многочлена 7-й степени с коэффициентами 1, 0, 0, 1, 1,0, 1,0 соответственно, т.е. х 7 + х 4 + х 2 + х.
Операции в циклических кодах можно рассматривать как с точки зрения операций над двоичными числами, так и с точки зрения операций над полиномами. При вычислениях используют операции сложения и деления полиномов. Сложение осуществ-
Деление также выполняется обычным образом, только операция вычитания заменяется сложением по модулю 2:
В циклических кодах разрешенные комбинации имеют два важных с точки зрения реализации свойства:
- 1. Для разрешенной комбинации циклический побитовый сдвиг приводит к разрешенной комбинации. Именно этот факт и послужил основой для названия метода.
- 2. Все разрешенные комбинации (в полиномиальном представлении) делятся без остатка на некоторый полином Р(х).
Полином Р(х) называют образующим или порождающим полиномом. Вид образующего полинома определяется желаемой разрядностью остатка и способностью определять ошибки. Число проверочных бит обычно совпадает со степенью порождающего полинома. Младший и старший биты Р(х) должны быть равны 1. Имеются и другие требования к образующему полиному. Некоторые конкретные порождающие полиномы определены в стандартах международных организаций.
Алгоритм построения циклического кода (кодирование передаваемых данных) имеет следующий вид:
- 1. Передаваемый ^-битовый блок данных умножается на число 2 Г . Данная операция равносильна умножению полинома D(x), соответствующему А:-битовой последовательности, на полином х г . В результате длина битовой последовательности увеличивается на г разрядов, причем эти последние г разрядов (блок FCS) заполнены нулями.
- 2. Полученная последовательность бит (как информационных, так и проверочных) делится на образующий многочлен Р(х) с остатком Q(x). Количество разрядов остатка на единицу меньше, чем у Р(х).
- 3. Полученный остаток Q(x) складывается с полиномом D(x)x r . Данная операция равносильна размещению в битах FCS коэффициентов полинома Q(x). Полученная новая битовая последовательность (кадр) Т(х) = D(x)x r +Q(x) и должна быть передана но сети.
Нетрудно видеть, что передаваемый кадр должен делиться на образующий полином без остатка. Действительно, если некоторое число (делимое) делится на делитель с остатком, то при вычитании остатка из делимого полученный результат будет без остатка делиться на делитель. Если, например, разделить в десятичной системе счисления 210 278 на 10 941, то получится остаток 2 399. Если вычесть полученный остаток из делимого (210278), то результат 207879 будет нацело (т.е. без остатка) делиться на 10941.
Пример 5.4. Рассмотрим передачу блока данных 1011101. Этому блоку соответствует полином D(x) = х 6 + х 4 + х 3 + х 2 + 1. Пусть в качестве образующего полинома выбран Р(х) = х 4 4- х 4- 1, которому соответствует число 10011. Количество проверочных бит совпадает со степенью полинома Р(х), т.е. г = 4, последовательность передаваемых данных будет содержать п = 7 4- 4 = 11 бит.
Выполним умножение полинома D(x) на полином х 4 :
что соответствует битовой последовательности 10111010000.
Произведем деление полинома D(x)x 4 на образующий полином:
Остаток от деления D(x)x x на Р(х) равен Q(x) = х 2 + х, что соответствует числовому значению 110, которое и будет размещено в поле проверочных бит (так как их количество г = 4, то будет размещено число ОНО).
Передаче подлежит кадр, который в виде полинома является суммой Т(х) = = D + Q(x) = х 10 И- х 8 + х 7 + х 6 + х л 4- х 2 4- х, что соответствует числовому значению 10111010110.
Осуществим проверку, выполнив деление Т(х) на Р(х):
Таким образом, если был получен кадр 10111010110, то принимается решение, что ошибок при передаче не произошло. В противном случае полагается, что в данных имеются искажения. ?
Рассмотренный метод циклического избыточного контроля обладает большей вычислительной сложностью, нежели контроль но паритету и применение контрольных сумм, но имеет гораздо более высокие диагностические возможности. Кодирование CRC позволяет обнаружить все битовые ошибки, все двойные, ошибки нечетной кратности, а также пакетные ошибки. Вероятность нахождения ошибок оценивается в 99,9984%. Избыточность метода считается невысокой. Например, кадр в 1024 бит может иметь контрольные данные размером в 4 бита, что составляет 0,4%.
Дальнейшим развитием метода циклического избыточного контроля является ЕСС-коитроль (контроль достоверности с исправлением ошибок, Error Correction Code), позволяющий не только обнаруживать, но и исправлять некоторые ошибки.