Галкин В.А., Григорьев Ю.А. Телекоммуникации и сети

Подождите немного. Документ загружается.

Основы

телекоммуникации

Рассматривая разрешенную комбинацию [п, А:]-кода

как

линейную комби-

нацию кодовых вектор-строк порождающей матрицы

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

(2.43)

равенство (2.46), получаем

+ g,(v^xHl,)

+ ... + g/v,,

V X

Hi,) = 0.

(2.48)

Из этого выражения очевидно: чтобы для любой разрешенной кодовой ком-

бинации

[п,

^]-кода выполнялось равенство (2.46), необходимо

достаточно,

чтобы вьшолнялось равенство:

Н1,=

0,илиС„,хН1,= 0. (2.49)

Это равенство устанавливает связь между порождающей

проверочными

матрицами [«, А:]-кода,

по нему можно определить одну из них, если известна

другая.

Если

какой-либо строке v. порождающей матрицы

G^^

прибавить линей-

ную комбинацию других строк,

то от

этого

она не

изменится

(в том

смысле,

что останется порождающей матрицей того

же

самого [п,к]'Кот). Действи-

тельно, пусть строка

матрицы

G^^

заменена строкой

УД

являющейся суммой

строки

и линейной комбинации других строк:

a,v,

+ a,v, +

...

v,.+ ...

a,v,. (2.50)

Посмотрим, какое влияние оказывает такая модификация порождающей

матрицы на общий вид разрешенной кодовой комбинации. Запишем разрешен-

ную кодовую комбинацию

общем виде:

g,v, +^2^2

+ ...

+g.y.+

... +

g,y,, (2.51)

где^.

е {О, 1};/= 1,2,..., Л.

После замены строки

у на

строку

у/

получаем:

= g,v, +

g^v^

... +

g.(a,y,

a^v^

+ ... +

+ ...

-+-

a^v^)

+ ... +

g^v^

= (g,

g^ciX

(^2

ЯЛ>2

+ - +

g.^i

+ - +

(gk

gPkK (2.52)

Так как коэффициенты

(g^

+ g.a) e{0,

1},

у = 1,2,..., к, то

общий вид разре-

шенной кодовой комбинации не изменился и матрица с новой строкой

У/

порож-

дает тот же самый код. Отсюда следует, что при сложении попарно,

по

три,

по

четьфе и

т.

д. кодовых комбинаций

записи полученной суммы на место одно-

го

из

слагаемых изменяется лишь

вид

матрицы,

но не

затрагивается

ее сущ-

2.2. Методы защиты от ошибок и

сэюатия

данных

ность, т. е. матрица, претерпевшая указанную операцию, порождает тот же

набор разрешенных кодовых комбинаций, что и исходная матрица.

Путем замены строк матрицы О^^ъ соответствии с формулой (2.52) можно

от любого ее вида перейти к каноническому виду:

<J^«,t =

0 .

1 .

0 .

.. 0

. 0

. 1

Ъи

К^

6,2

*22

Кг

Ьгг

^2г

''кг

(2.53)

Здесь информационные разряды

порождающей матрице канонического вида

представлены единичной подматрицей.

Пусть подматрица информационных разрядов порождающей матрицы име-

ет вид:

А^

а. а

а.

2к

к\

к2

кк

(2.54)

Здесь все вектор-строки линейно независимы. Предположим, что это не

так и существует строка v., которая может бьггь выражена в виде линейной

комбинации остальных строк. Представим строку

через сумму других строк

и запишем

на место какой-либо строки, входящей слагаемым в данную сум-

му. Таким образом, если верно наше предположение, то в подматрице А могут

существовать две одинаковые строки, что, в свою очередь, влечет за собой

равенство соответствующих проверочных

разрядов,

так как должно вьшолнять-

ся равенство (2.36). В результате получаем, что наличие в подматрице А ин-

формационных разрядов линейно зависимых строк влечет за собой наличие в

порождающей матрице линейно-зависимых строк. Но так как, по определению,

в порождающей матрице все строки независимы, то и в подматрице А этой

матрицы не может существовать линейно зависимых строк.

Линейно независимые вектор-строки матрицы А порождают Л-мерное ли-

нейное пространство, содержащее

элементов, которое может быть вьфаже-

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

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

1 О

О 1

(2.55)

Основы телекоммуникации

Канонический вид порождающей матрицы удобен

тем,

что существует про-

стая связь между элементами порождающей и проверочной матриц: для опре-

деления проверочной матрицы

[п,

к]

-кода, порождаемого матрицей вида (2.53),

нужно транспонировать подматрицу проверочных разрядов матрицы G^

и при-

писать справа к полученной матрице единичную матрицу размерности г х г.

Таким образом, матрице (2.53) соответствует проверочная матрица (2.45).

Коды Хэмминга. К систематическим корректирующим [п, А:]-кодам

относятся коды Хэмминга с кодовым расстоянием rf = 3. Из табл. 2.2 видно,

что число разрешенных кодовых комбинаций для кодов с ^ =

равно

Л^<

2"{

+ пук Для кодов Хэмминга выбрано предельное значение разрешенных кодовых

комбинаций

7V=

2"(1 + пУ\ а число информационных разрядов к определяется

как:

к = log[2Xl + пУ] =

дг

- log

+ 1).

(2.56)

Данное уравнение имеет целочисленные решения А:=0,1,4,11,26,..., которые

и определяют соответствующие коды Хэмминга [3,1

]-код,

[7,4]-код, [15,11 ]-код

и т. д.

Рассмотрим, в качестве примера, построение [7,4]-кода. Для этого восполь-

зуемся каноническим представлением (2.53) порождающей матрицы

Под-

матрица проверочных разрядов этой матрицы должна состоять из различных

ненулевых строк. Определим зависимость числа проверочных г и информаци-

онных к разрядов для кодов Хэмминга:

= 2^1 + пУ или 241 + «)= 2*2^

учитьшая, что п = к + г, получим к

г + I =2'' или к

Т- г - 1.

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

кодовой комбинации равно

2^^

- 1, из них г следует вьпесть для образования

единичной матрицы г х г, которую следует добавить к транспонированной

матрице проверочных разрядов при определении проверочной матрицы

Hnk. Тогда остается (2'^-г-1)г-разрядных

строк

числом единиц

не

менее

двух.

Это

число равно числу информационных

разрядов А. Распределение ненулевых

строк для [7,4]-кода представлено на рис.

2.14. В этом случае порождающая мат-

рица будет содержать единичную под-

матрицу размерностью

А:

х /: и подмат-

рицу проверочных разрядов размерностью

г\

Для единичной

подматрицы проверочной

матрицы

Для проверочных

разрядов в порождающей

матрице

Рис. 2.14. Распределение ненулевых

строк [7,4]-кода

2.2.

Методы защиты от ошибок

сжатия данных

GiA-

10 0 0 0 1 1

0 10 0 10 1

о 1 о 1 1 (^

0 0 0 1111

(2.57)

Проверочная матрица строится путем транспонирования подматрицы про-

верочных разрядов порождающей матрицы и добавления единичной подмат-

рицы

у.

г:

10 1 1 1 1 О 01

^7,4 -

1 о 1 1 о 1 0|

110 10 0 1

(2.58)

Из этой

проверочной

матрицы легко

получить систему проверок, связьюаю-

щую проверочные и информационные разряды кода по формуле (2.36). Хэм-

минг предложил размещать проверочные разряды в позициях кодовой комби-

нации, кратных целой степени двойки, это позволяет по виду синдрома сразу

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

декодирования на примере [7,4]-кода Хэмминга.

Алгоритм

кодирования.

Все номера позиций кода нумеруют в двоичной

системе счисления, начиная с единицы р-разрядным двоичным числом:

р = flog п\, где

1 - ближайшее большее целое, п - число разрядов кода

с с

п п-

...С....С,.

Проверочные разряды размещают

позициях кода, кратных целой степени

двойки 2^ 2', ...их

д.:

с =6 ,7

2',

/=0,1,...,

(г-1),

где

г-число

проверочных

разрядов. Значение с проверочного разряда определяется как сумма по mod2

тех разрядов кода, в номере которых двоичный разряд с /-м весом равен еди-

нице.

Пример. Пусть информационный кодовый вектор

1101.

В коде Хэмминга этот вектор,

начиная

младшего разряда, буцет занимать позиции

Cj, Cj,

с^

с^,

а позиции

Cj,

с^, с^

отводятся

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

^m^iio^ioif^ioJ^oiiKiJf^ooJ ^ выделим позиции для размещения проверочных разрядов:

^111

^101

^100

^011

' 1

^010

^001

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

кода, в номере которых двоичный разряд

I-M

весом равен единице:

/ = 0-^2°->с^,=с<,„Фс,„,ес,„;

(2.59)

= 2->2^-»с,^ = с.„.

•'^по® «^п,;

Основы телекоммуникации

Таким

образом,

получен кодовый вектор v

'= 1100110,

который

передают

по

каналу,

подвер-

женному

влиянию

помех.

Пусть вектор ошибки равен е =

0000100,

тогда принятая из

дискретно-

го канала кодовая

комбинация будет

иметь

внц:

v"= 1100010 = v' е е. (2.60)

Алгоритм декодирования. Вычислим значение синдрома ошибки:

^оо.

= РЛ_,...А,-Л11- (2-61)

Значение /-го разряда синдрома определяется как сумма по mod2 тех раз-

рядов принятого кода, включая проверочные, в номере которых вес двоичного

разряда совпадает с весом разряда синдрома:

^=^00,

Ф^оп Ф '^.о.® '^п,;

^2=^0,0*^0,.® '^ПО® ^ПР

^3=^,00® ^,0,® ^ПО® ^ПГ

awepa v" =1100010:

Л,

Ф С5Ф с,= 0 Ф 0 Ф 0 Ф Ь

Н^=

с^

Ф с^Ф Cj= 1 Ф 0 Ф 1 Ф 1

А =

с^

Ф с, Ф с^Ф с= 0 Ф 0

1 Ф 1

3 4 5 6 7

= 1;

= 0.

(2.62)

(2.63)

Синдром ошибки Е^^ = II ^3^2^111 "^

1|011|1

определяет в двоичной системе

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

ошибки необходимо инвертировать третий разряд - с^ кодового вектора:

v" = 1100110, откуда, выделяя информационные разряды, получаем исходный

кодовый вектор v = 1101.

Циклические коды. Линейный [«, Л]-код называют циклическим, если в

результате любого циклического сдвига кодового вектора получают другой ко-

довый вектор, т. е. если v =

а^а^

а^..,

а^^- кодовый вектор, то v' = а^^а^а^,,

а^2 ~ другой кодовый вектор.

Представим кодовый вектор v = а^а^

а^,„

а^^ полиномом степени {п - \)

или меньшей степени: v (дс) =

ci^^x^^

+...+ а^^ +

а^х

а^- кодовый полином.

Рассмотрим двоичные циклические коды, в которых основание х выбирают

равным двум, а операция суммирования ведется по mod2. Для кодирования

циклическим кодом используются так назьгоаемые порождающие полиномы

(« - Л)-степени. Пусть необходимо закодировать сообщение, представленное в

виде кодового полинома т{х) = 'w^.,^"* + ... + т^х + /w^, где к - количество

информационных разрядов. Умножив т{х) на л:'^*, получим полином степени

{п - к) или меньшей степени:

х'^''т(х)

т^_^х'*-^

н-... +

т^х'^'^^

+ т^'^^ (2.64)

2.2. Методы защиты от ошибок и сжатия данных

Разделим (2.64) на порождающий полином

g{x)

степени

{п

к):

x'^-'mix)

= q(x)g(x) + р(х\ (2.65)

где д(х) - частное, p(jc) - остаток.

Так как степень полинома g(x) равна (п - к), то степень остатка должна

быть равна (п- к- 1) или быть меньше:

Р.-,-,^"-'-^

+ .-. +

Р2^'

+ Р,^+

Ро-

(2.69)

Формулу (2.65) можно представить в ином виде, где левая часть уравнения

кратна

g(x):

р(х) '^x"-'m(x)=q(x)g{xr (2.70)

Раскроем (2.70) с учетом (2.64) в виде полинома степени (п - 1):

х"~''т(х)

р(х)

т^_^х"~^

+ ...+

т^х"~^'^^

т^"'^

+ Р„.,.,^''-'-^+...+

Р,^+Ро.

^^'^^^

в данном виде формула (2.71) соответствует кодовому вектору v =

= m^_j.../Wj/WQp^_^ J... р2Р,Р,

•

Отсюда следует, что циклический код информа-

ционного сообщения

т(х)

состоит

из

неизменного сообщения

т^

^...т^т^

при-

соединенного к нему остатка

p^_^_j...

PjP^.

Важным свойством циклического [л, Л]-кода является то, что порождаю-

щий полином

g{x)

является делителем для полинома

л:"

+ 1:

л:^

+ 1 =

g{x)h{x),

где h{x) - проверочный полином. Зная h{x) можно однозначно определить

порождающий полином g{x). Например, для циклического кода [7,4]

g(л:)=l+л:+x^ Л(л:)= ^ ^^

=х''

х'

х-\- 1.

XH-JC + 1

Существует теорема, которая доказывает, что если

g{x)

- полином степени

[я,

к]

является делителем для полинома

дс^

то g{x)

порождает циклический

[я,

А:]-код. Действительно, любой делитель х" + 1 степени {п - к) может по-

рождать циклический

код.

Для больших п выражение

л:"

может иметь мно-

го

делителей степени

{п

к).

Некоторые

из

них порождают эффективные коды,

а некоторые - нет.

Обычно в качестве порождающего полинома выбирают

примитивный

по-

лином степени г

{п-к) из числа

неприводимых

полиномов той же степени.

Полином/7(л:)

степени г с

коэффициерггами,

принимающими

значение из

множе-

ства

{0,1},

является

неприводимым^

tcjmp{x) не делится ни на один полином

с двоичными положительными коэффициентами степени, меньшей чем г (де-

лятся только на единицу и на самого себя).

Неприводимый полином р{х) степени г называют

примитивным

тогда и

только тогда, когда

л^

не делят на/7(л:) для я <

2'^

- 1, т. е.:

Основы

телекоммуникации

jc"

+ 1 = g(x)h(x)

ДЛЯ

п = Т - I; (2.72)

х"-^

I 4t g(x)h(x) цляп <r - I. (2.73)

Примеры примитивных полиномов:

г= 16 jc^^ +

л:^2

Д.З

+д;4- 1.

Процедуру кодирования циклическим кодом можно разбить на три шага:

• умножить исходный кодовый полином т(х) =

гп^_^х^~^

+ ... +

т^х

+ т^ на

^п-к ^

xj^Q соответствует сдвигу кодового вектора в сторону старших разрядов

на (п - к) разрядов:

х'^''т(х)

гп^^х*^^

+ ... + WjX'^*^^ + т^"~^\

• получить остаток р(л:) от деления

;c'^*/72(jc)

на порождающий полином g{x)\

• вьшолнить операцию конкатенации полученного кодового вектора остатка

р(х) и исходного кодового вектора полинома т{х): т^ ^...т^т^р^^

^,„

p2piPo-

Декодирование циклического кода заключается в следующем. Пусть v(jc) -

передаваемый кодовый полином, г(х) - принятый кодовый полином. Разделив

г(х) на порождающий полином

g(x),

получим:

r{x) = g(x)q(x)-^s(x% (2.74)

где ^(л:) - частное, s(x) - остаток.

Если остаток равен нулю, т. е. принятый кодовый вектор кратен порождаю-

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

остаток не равен нулю, то принятый кодовый вектор не является кодовым по-

линомом, т. е. содержит ошибку. Таким образом, ненулевой остаток определя-

ет наличие ошибки, т. е. представляет собой ее синдром:

s(x) =

s^k-i^'^'"^

+.,.+ s^x +

s^,

(2.75)

Пусть полином вектора ошибки имеет вид:

е(х) =

е^^х"-'

+...

е^х^

+ е^, (2.76)

тогда г(х) = v(jc) + е(х) или с учетом (2.74):

e(x) = v(x)

q{x)g(x)-\-s(xy (2.77)

Так как v(x) - кодовый полином, кратный g(x), т. е. v(x) = m(x)g(x), то :

е(х) =

[т(х)

+ q(x)]g(x)

s(x), (2.78)

Отсюда видно, что синдром s(x) является остатком от деления полинома

вектора ошибок е(х) на порождающий полином g(x). Функция декодирующего

устройства заключается в оценке полинома вектора ошибки е(х) по синдрому

s(x).

2.2. Методы защиты от ошибок и сжатия данных

Для

различных сочетаний одиночных ошибок

кодовой комбинащш двоич-

ного циклического [7,4]-кода соответствующие им синдромы представлены в

табл.

2.2.

Рассмотрим пример двоичного циклического [7,4]-кода (« = 7,

А:

= 4). По-

рождающим полиномом такого кода является примитивный полином степени

\n-k):g{x) =

+л: + 1.

Таблица

2.2.

Определение

синдрома одиночной ошибки кода

[7,4]

Ошибка

е{х)

х"

\ х'

х'

Синдром s(x)

х"

х'

х+1

х^+.х

х^+

х+

х'+1

Вектор синдрома

53 1 52 1 5,

0 0 1

0 1 0

10 0

0 1 1

11 0

11 1

1 0 1 1

Пусть необходимо закодировать кодовый вектор с

А:

= 4 1101. Представим

его в виде полинома степени к- I: т(х) =

д:^

jc^

+ 1.

Кодирование. Операция кодирования состоит из трех шагов.

Умножим т(х) на

л:""*:

т(х)х^

(jc^

jc^

l)x^

х^

jc^,

что соответ-

ствует сдвигу кодового вектора

сторону старших разрядов на (п - к) разряда

и добавлению

освободившиеся разряды

нулей:

1101000.

Разделим

т(х)х^

на g(x):

/ +х^ +

х^+

х'+х'

х'

х^

дг^+д:

+ 1

+х^ +х

+х

1-ос

таток

ИЛИ

1101000

1011

1100

1011

1110

1011

1010

1011

001-

|1011

1111

- остаток

Таким образом, остаток р(х) = р^.

Припишим остаток

информационным разрядам:

v(jc) =

т{х)х^''

p(x) =

л:^

д:^

Основы

телекоммуникации

ИЛИ

выполняем операцию конкатенации исходного кодового вектора и вектора

остатка:

1101.001,

в результате получаем циклический [7,4]-код.

Декодирование. Пусть вектор ошибки равен е{х) = х^, тогда принятый по-

лином будет иметь вид:

г(х)

у(х) +e(jc) =jc^ + jc5+;c^+jc3+l или 1101001+0010000=1111001.

Для обнаружения ошибки необходимо разделить принятый полином на по-

рождающий:

X^+JC^+X^+X^+ 1 X^+X + l

х^

+ дс^+х^

х^+х^+1

х'

1111001 [1011

1011 1101

1000

или 1011

х^+х^ +1 1101

х'

4-х +1 1011

х^ +

- синдром 110 - вектор синдрома

Из таблицы 2.2 по виду синдрома определяем место ошибки - разряд с ве-

сом 4.

Эффективность циклического кода. Так как порождающий полином g(x)

имеет степень (п - к), то существует кодовый вектор, являющийся пакетом

длиной (« -

А:

+1), т. е. содержащий (п - к+\) единиц подряд. Если полином

вектора ошибки е(х) представляет собой пакет длиной (п - к) или меньшей, то

согласно вьфажению е(х) = [т(х) + g(x)]g(x) + s(x) синдром никогда не будет

равен нулю. Это означает, что циклический [«, к]- код пригоден для обнаруже-

ния любого пакета ошибок длиной (п - к) или меньшей, а также отдельных

пакетов и большей кратности. Доля необнаруженных пакетов ошибок длиной

{п-к+ 1) составляет 2

"^''"*"

^>,

а длиной более {п-к+ I)- 2"^''"*>. Приведен-

ный анализ показьюает, что циклические коды весьма эффективны для обнару-

жения ошибок, поэтому их широко применяют

системах телекоммуникации.

Логический код 4В/5В. Наряду с циклическими кодами, которые исполь-

зуют, как правило, на канальном и вьппе уровнях модели OSI, для улучшения

потенциальных кодов типа AMI, NRZI или 2B1Q используют другие избьггоч-

ные логические

коды.

Логическое кодирование должно заменять длинные пос-

ледовательности

бит,

приводящие к постоянному потенциалу в среде передачи

данных, вкрапле1шями

единиц.

Как отмечалось

вьппе,

для логического кодиро-

вания характерны два метода - избыточные коды и скрэмблирование. Напри-

мер,

избьггочный логический код 4В/5В, используемый в технологиях FDDI и

Fast Ethernet, заменяет исходные символы длиной 4 бит на символы длиной в 5

бит. Так как результирующие символы содержат избыточные биты, то общее

2.2.

Методы защиты от ошибок и сжатия данных

количество битовых комбинаций в них больше, чем в исходных. Так, в коде

4В/5В результирующие символы могут содержать 32 битовых комбинации, в

то время как исходные символы - только 16. Поэтому в результирующем коде

можно отобрать

таких комбинаций, которые не содержат боль-шого количе-

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

Кроме устранения постоянной составляющей и придания коду свойства само-

синхронизации, избыточные

коды

позволяют приемнику распознавать искажен-

ные биты. Соответствие двоичного кода коду 4В/5В представлено в табл. 2.3.

Код 4В/5В передается по линии с помощью физического кодирования по одно-

му из методов потенциального кодирования, чувствительному только к длин-

ным последовательностям нулей. Символы кода 4В/5В длиной 5 бит гаранти-

руют, что при любом их сочетании на линии не могут встретиться более трех

нулей

подряд.

Буква В в

названии

кода

означает,

что

элементарный сигнал имеет

2 состояния (от английского binary - двоичный). Существуют коды и с тремя

состояниями сигнала, например,

коде 8В/6Т

для

кодирования 8 бит исходной

информации используется код из 6 сигналов, каждый из которьпс имеет три

состояния. Избыточность кода 8В/6Т вьппе, чем у кода 4В/5В, так как на 256

исходных кодов приходится 3^= 729 результирующих символов.

Таблица

2.3.

Соответствие двоичного

кода коду 4В/5В

Двоичный код

0000

0001

0010

ООП

0100

0101

ОНО

1111

Код4В/5В

НПО

01001

10100

10101

01010

01011

OHIO

они

Двоичный код

1000

1001

1010

1011

1100

1101

1110

1111

Код4В/5В

10010

10011

ЮНО

10111

НОЮ

11011

11100

11101

Использование для перекодировки таблицы, аналогичной

табл.

2.3, являет-

ся простой операцией, поэтому это не усложняет сетевые адаптеры и интер-

фейсные блоки коммутаторов и маршрутизаторов.

Для обеспечения заданной пропускной способности линии передатчик, ис-

пользующий избыточный

код,

должен работать с повышенной тактовой часто-

той.

Так, для передачи кодов 4В/5В со скоростью 100 Мбит/с необходима так-

товая частота передатчика 125 МГц. При этом спектр сигнала на линии

расширяется по сравнению со случаем, когда по линии передается чистый, не

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

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

этап логического кодирования, а также работу приемника и передатчика на

повьппенной тактовой частоте.