Лекции по "Основы построения телекоммуникационных систем"

Помехоустойчивый код характеризуется  тройкой чисел (n, k, d),

где n –общее число разрядов в передаваемом сообщении, включая проверочные разряды –r,  k=n-r  число информационных разрядов,

d – определяет число обнаруживаемых ошибок, как d-1; или число исправляемых ошибок, как (d-1)/2

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

(a₀a₁…a_n-1)

(a_n-1a₀a₁… a_n-2)

………..

 

циклические коды задаются с помощью  порождающих полиномов g(x)

 

G(x)= g_rx^r + g_r-1x^r-1 + … + g₀ ,                                 где      g_i = { 0,1}, x = 2

 Кроме того, вводится понятие  полинома исходного сообщения

 

U(x) = u_k-1 x^k-1 + u_k-2 x^k-2 + … + u₀

 

И полинома кодированного сообщения

 

A(x) = a_n-1 x^n-1 + a_n-2 x^n-2 + … + a₀

Рассмотрим последовательность кодирования  на примере циклического кода (7,4,3), имеющего      g(x) = x³ + x + 1        n = 7, k = 4, d = 3, r = 3 

 

1. Информационная часть сообщения записывается в виде полинома

U(x) = u_k-1 x^k-1 + u_k-2 x^k-2 + … + u₀

 

В рассматриваемом примере  k=4 и для сообщения 0111 получаем

U(x) = x² + x + 1 

2. u(x) умножается на x^r,  что соответствует циклическому сдвигу исходного сообщения на  r разрядов влево:

u(x) x^r = (x² + x + 1) x³ = x⁵ + x⁴ + x³

2. Полученный многочлен делится на g(x)

 

Где с(х) – полином- частное с  максимальной степенью (k-1); R(x) – полином с максимальной степенью (r-1);         Å   -поразрядное суммирование по модулю 2

 

Кодированное сообщение представляется в виде A(x) = u(x) x^r Å  R(x)

Т.е. на месте младших, освобожденных  после умножения на х , разрядов, записываются проверочные разряды a_r-1, a_r-2, a₀

Для рассматриваемого примера

 x⁵ + x⁴ + x³ x³ + x + 1

 Å x⁵ + x³ + x²   x² + x  =c(x)

x⁴ + x² 

• x⁴ + x² + x 

x = R(x)

Таким образом, в данном случае А(х)  = (x⁵ + x⁴ + x³) Å x = x⁵ + x⁴ + x³ + x

 

Передаваемое кодированное сообщение в обычной двоичной форме имеет вид

0 1 1 1 0 1 0

 

k-бит r-бит

 

При получении кадра  данных снова вычисляется остаток от деления на тот же делитель, но при этом к данным кадра добавляется и содержащаяся в нем контрольная сумма. Если остаток от деления на R равен нулю, то делается вывод об отсутствии ошибок в полученном кадре, в противном случае кадр считается искаженным. Метод CRC обнаруживает все одиночные ошибки, двойные ошибки и ошибки в нечетном числе бит. Метод обладает невысокой избыточностью: для кадра Ethernet размером 1024 байт контрольная информация длиной в 4 байт составляет 0,4 %

 

Методы восстановления искаженных и потерянных кадров

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

Существует 2 подхода к организации  процесса обмена квитанциями

• Метод с простоями (Idle Source) новый кадр посылается только после получения квитанции от приемника. Если квитанция не приходит , то повторяется предыдущий кадр. Недостаток- значительное снижение скорости передачи данных., особенно заметно на низкоскоростных каналах связи.
• торой метод называется методом скользящего окна(sliding window)/ В этом методе для повышения коэффициента использования линии источнику разрешается передать некоторое количество кадров в непрерывном режиме без получения квитанций. Количество кадров, которое разрешается передать при этом, называется размером окна.

 w₁  w_n

 w₀

 …  … … …

 

 

…

 

 

 t₀ t₁  t_n

 

 

 

w₀=w₁=w_n

w_n

t_n

Направление скольжения окна

 w₁

t₁

w₀

t₀

 

1     2     3 n+1 w    w+1  w+n Номера кадров

 В момент t₁ при получении 1-й квитанции К1 окно сдвигается на 1 позицию, определяя новый диапазон от2 до (w+1)/

Процессы отправки кадров и получения  квитанций идут достаточно независимо друг от друга. Рассмотрим произвольный момент времени t_n, когда источник получил квитанцию на кадр с номером n. Окно сдвинулось вправо и определило диапазон разрешенных к передаче кадров от (n+1) до (w+n).Все множество кадров, выходящих из источника, можно разделить на группы

• Кадры с номерами от 1 до n были уже отправлены и квитанции на них получены, т. е. они находятся за пределами окна слева.
• Кадры, начиная с номера (n+1) и кончая номером (w+n) находятся в пределах окна, и потому могут быть отправлены не дожидаясь прихода какой-либо квитанции. Этот диапазон может быть разделен еще на 2 поддиапазона.

-Кадры с номерами от  n+1 до m, которые уже отправлены, но квитанции на них еще не получены.

                  - Кадры с номерами от m до w+n, которые пока не отправлены, хотя запрета на это нет

• Все кадры с номерами, большими или равными (w+n+1), находятся за пределами окна справа и поэтому не могут быть отправлены.

Итак, при отправке кадра с номером  n источнику разрешается передать еще w-1 кадров до получения квитанции за кадр n, так что в сеть последним уйдет кадр с номером (w+n-1).  Если же за это время квитанция за кадр n так и не пришла, то процесс передачи приостанавливается, и по истечении некоторого тайм-аута кадр n считается утерянным, и он передается снова.

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

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

 

В надежных сетях размер окна можно  увеличивать, в ненадежных  - уменьшать