ARQ - методы повторной передачи.

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

 

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

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

 

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

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

 

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

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

Обработка ошибок. Результаты теории кодирования.

Результаты теории кодирования.

Теория кодирования Хемминга. Простые коды характеризуются тем, что для передачи информации используются все кодовые слова (комбинации), количество которых равно N=qⁿ (q - основание кода, а n - длина кода. Тогда задача кодирования заключается в получении при передаче для каждой k - элементной комбинации из множества q^k соответствующего ей кодового слова длиною n из множества qⁿ . Задача декодирования состоитв получении k - элементной комбинации из принятого n - разрядного кодового слова при одновременном обнаружении или исправлении ошибок

 

Параметры помехоустойчивых кодов:

1. Длина кода –n
2. Длина информационной последовательности –k
3. Длина проверочной последовательности – r = n –k
4. Скорость кода – R = k/n
5. Избыточность кода – 1/R
6. Кодовое расстояние между двумя кодовыми словами (расстояние Хэмминга) - это число позиций, в которых они отличаются друг от друга.
7. Кодовое расстояние кода d₀- это наименьшее расстояние Хэмминга между различными парами кодовых слов

Основные результаты. Основные зависимости между кратностью обнаруживаемых ошибок t_о, исправляемых ошибок t_u, исправлением стираний t_c и кодовым расстоянием d₀ кода:

d₀ ≥ t₀ + 1; d₀ ≥ t₀ + t_u + 1 (при t₀ > t_u );

d₀ ≥ 2 t_u + 1; d₀ ≥ 2 t_u + t_c + 1

d₀ ≥ t_c + 1;

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

 

Граница Хэмминга близкак оптимальной для высокоскоростных q-ичного и двоичного кодов

n – k ≥ log_q ∑ _{i = 0…tu} ( C_nⁱ  * ( q - 1)ⁱ );

 

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

Позволяет обнаруживать однократные ошибки (в случае нескольких – нечетное количество).

 

Ещё количество ошибок можно уменьшить введением бита паритета.

 

 

Полиномиальное кодирование (CRC).

 

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

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

CRC коды построены на рассмотрении битовой строки как строки коэффициентов полинома. k-битовая строка соответствует полиному степени k − 1. Самый левый бит строки — коэффициент при старшей степени. Например, строка 110001 представляет полином x5 + x4 + x0. Коэффициенты полинома принадлежат полю вычетов по модулю 2.

Основная идея заключена в том, чтобы пересылать только такие сообщения, полиномы которых делятся на некоторый фиксированный полином G(x). Если мы получаем сообщение, что чей –то полином не делится на G(x), значит при передаче сигнал был искажен. Мы не заметим ошибок, если они один допустимый полином (то есть полином делящийся на G(x)) преобразовали в другой допустимый полином. Полином G(x) тем лучше, чем больше среднее расстояние Хемминга на парах допустимых полиномов.

 CRC используется добавление к нашему сообщению некоторого количества бит так, чтобы результирующий полином делился на G(x).

⇐ Предыдущая123456Следующая ⇒

Поделиться: