Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

ЛЕкции - Передача дискретных сообщений - файл Zu_K_PDS.doc


ЛЕкции - Передача дискретных сообщений
скачать (98.3 kb.)

Доступные файлы (1):

Zu_K_PDS.doc500kb.09.12.2006 02:19скачать

Zu_K_PDS.doc

1   2   3   4   5


Общее число кодовых комбинаций N0=2n=27=128, из них разрешенных Na=2k=24=16. Четыре из них являются строками производящей матрицы, пятая - нулевая, а остальные одиннадцать находятся суммированием по модулю два различных строк производящей матрицы G7,4.

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

Найдем проверочные элементы, пользуясь матрицей проверочных элементов B3,4. Согласно приведенным выше правилам


b1=a2a3a4 ,

b2=a1a3a4 , (2.1)

b3=a1a2a4 .


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

Пример 2.4. Переданная кодовая комбинация имеет вид 1000011 (первая строка матрицы G7,4). В результате действия помех на приемном конце имеем a1’, a2’, a3’, a4’, b1’, b2’, b3’=1100011. Произведем проверки (2.1):


a2a3a4’=100=1=b1* ,

a1a3a4’=100=1=b2* ,

a1a2a4’=110=0=b3* .


В то же время b1’=0, b2’=1, b3’=1, т.е. b1* b1’ , b3* b3’ , что говорит о наличии ошибок в принятой кодовой комбинации. При отсутствии в принятой кодовой комбинации ошибок b1* b1’=c1=0, b2* b2’=c2=0, b3* b3’=c3=0.

Комбинация с1 с2 с3 называется синдромом (проверочным вектором). Равенство нулю всех элементов синдрома указывает на отсутствие ошибок, или на то, что кодовая комбинация принята с ошибками, которые превратили ее в другую разрешенную. Последнее событие имеет существенно меньшую вероятность, чем первое.

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

Рассмотренный код (7,4) гарантированно обнаруживает двухкратные ошибки, а исправляет только однократные. Матрица проверочных элементов B3,4 представляет собой набор синдромов - опознавателей одиночных ошибок. Первый синдром соответствует искажению элемента a1, второй - a2, третий - a3, четвертый - a4.


2.5. Циклические коды


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


F(x)=an-1 xn-1 + an-2 xn-2 +...+ a1 x + a0,


где коэффициенты ai равны 0 или 1, причем ai = 0 соответствует нулевым элементам комбинации, а ai = 1 - ненулевым. Например, комбинациям 1101 и 1010 отвечают полиномы F1(x)=x3 + x2 + 1 и F2(x)=x3 + x. Наивысшая степень полинома на единицу меньше числа элементов кодовой комбинации.

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


F1(x) F2(x)=(x3 + x2 + 1) (x3 + x)=x2 + x + 1,


поскольку x3x3=x3(11)=0.


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






x7

+

x5

+

x3

+

x2

+

1

x4

+

x

+

1
















































x7

+

x4

+

x3













x3

+

x

+

1























































x5

+

x4

+

x2











































































x5

+

x2

+

x


















































































x4

+

x

+

1











































































x4

+

x

+

1












































































0




0




0
















Разрешенные комбинации циклического кода обладают двумя очень важными отличительными признаками: циклический сдвиг элементов разрешенной кодовой комбинации дает также разрешенную комбинацию циклического кода. Все разрешенные кодовые комбинации делятся без остатка на полином P(x), называемый образующим. Эти свойства используются при построении циклических кодов, кодирующих и декодирующих устройств, а также при обнаружении и исправлении ошибок.

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

Полином Q(x), соответствующий k-элементной комбинации простого кода, умножаем на . Умножение Q(x) на необходимо, чтобы сдвинуть информационные элементы на r разрядов влево и тем самым высвободить справа r разрядов для записи проверочных элементов. Определяем проверочные элементы в виде остатка R(x) от деления произведения Q(x) на образующий полином P(x) степени r. Проверочные элементы прибавляем к Q(x). В результате получаем кодовую комбинацию n-элементного циклического кода


. (2.2)


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

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

Пример 2.5. Задан полиномом Q(x) = x3 + x, соответствующий четырехэлементной комбинации простого кода. Требуется построить комбинацию циклического кода с . Этому условию удовлетворяет циклический код (7,4) (см. пример 2.3). Возьмем в качестве образующего полинома P(x)=x3 + x + 1 и разделим Q(x)xr = ( x3 + x ) x3= x6 + x4 на x3 + x + 1:






x6

+

x4



















x3

+

x

+

1
















































x6

+

x4

+

x3













x3

+

1



































































x3























































































x3

+

x

+

1


















































































x

+

1

















Остаток от деления


R(x) = x + 1.


Соответственно полином комбинации циклического кода


F(x) = x6 + x4 + x + 1.


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

Циклические коды относятся к классу линейных кодов, которые могут быть заданы в виде произведения матриц Gn,k=|Ik Br,k|. В отличие от линейного кода, где матрица проверочных элементов определяется методом подбора строк с определенным весом, в циклических кодах матрица Br,k находится по общим правилам (2.2) с помощью деления строк матрицы Ik, сдвинутых на r разрядов влево, на образующий полином.

Производящая матрица циклического кода (7,4) (см. пример 2.3) может быть записана в виде






1

0

0

0

1

0

1


.

G7,4=



0

1

0

0

1

1

1




0

0

1

0

1

1

0




0

0

0

1

0

1

1




a1

a2

a3

a4

b1

b2

b3



Строки в матрице G7,4 содержат четыре комбинации циклического кода. Пятая комбинация является нулевой. Остальные одиннадцать комбинаций получаются суммированием по модулю два всех сочетаний строк матрицы G7,4.

Матрица проверочных элементов B3,4, как и для обычных линейных кодов, представляет собой набор синдромов – опознавателей одиночных ошибок. Первый синдром соответствует искажению элемента a1, второй – a2 и т.д.


^ 2.6. Системы с обратной связью


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

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

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

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

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

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

Системы с РОС получили наибольшее практическое распространение. Существуют различные разновидности таких систем.

Простейшая и довольно часто применяемая на практике структурная схема системы с РОС представлена на рис. 2.1.



Дискретный канал



Прямой канал

ИС


КОДЕР


ПЕРЕДАТЧИК


ПРИЕМНИК


ДЕКОДЕР


Н2


ПС





Н1

Обратный канал




ПРИЕМНИК


ПЕРЕДАТЧИК


УУ1


УУ2




Рис. 2.1



Алгоритм работы системы с РОС заключается в следующем. Источник сообщений ИС выдает в кодер первую кодовую комбинацию (или блок, состоящий из нескольких кодовых комбинаций). К исходным элементам в кодере добавляются проверочные. Комбинация выдается в дискретный канал и одновременно записывается в накопитель Н1 (накопитель передачи). После выдачи первой кодовой комбинации источник ждет ответа о том, как она принята.

Принятая кодовая комбинация декодируется. Информационные элементы записываются в накопитель приема (Н2). Если ошибка не обнаружена, то по команде управляющего устройства приема (УУ2) информационные элементы из накопителя Н2 выдаются получателю сообщений ПС, а по обратному каналу выдается сигнал «Да», подтверждающий правильность приема переданной кодовой комбинации (обратный канал будем считать идеальным). По сигналу «Да» управляющее устройство передачи (УУ1) стирает из Н1 кодовую комбинацию и дает разрешение на выдачу следующей кодовой комбинации. Если следующая кодовая комбинация исказилась и ошибки на приеме обнаружены, то по команде УУ2 информация из Н2 стирается, а по обратному каналу выдается сигнал «Нет». По этому сигналу на передающем конце УУ1 запрещает выдачу следующей кодовой комбинации от источника сообщений и дает команду о повторной выдачи из накопителя Н1 хранящейся там кодовой комбинации. Кодовая комбинация будет повторяться до тех пор, пока не придет сигнал «Да». Очевидно, что чем больше повторений на анализируемом интервале времени, тем хуже качество канала, тем больше длится «перекачка» сообщения от источника и тем ниже скорость передачи информации. Если в системе начинает циркулировать одна и та же кодовая комбинация – говорят, что система «зацикливается». С целью предотвращения «зацикливания» обычно ограничивают количество таких повторов. После некоторого числа повторов одной и той же комбинации система переводится в режим «авария».

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

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

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

В системах с РОС любого типа по обратному каналу передаются только сигналы решения и обратный канал имеет существенно меньшую пропускную способность.

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

^ КОНТРОЛЬНЫЕ ВОПРОСЫ




  1. Какие методы защиты от ошибок вам известны?

  2. Сформулируйте вторую теорему Шеннона.

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

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

  5. Какие коды называются линейными? Как они задаются?

  6. Как происходит обнаружение (исправление) ошибок в случае линейного кода?

  7. Чем отличаются циклические коды от линейных? Как строятся кодовые комбинации циклического кода? Как построить производящую матрицу циклического кода?

  8. Как происходит обнаружение (исправление) ошибок в случае циклического кода?

  9. Зачем используются системы с обратной связью? Охарактеризуйте системы с ИОС и РОС.

  10. Приведите алгоритм работы системы с РОС-ОЖ. Каковы достоинства и недостатки систем с ИОС и РОС?
1   2   3   4   5



Скачать файл (98.3 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации