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
Московский технический университет связи и информатики


Теория и техника телекоммуникаций

Учебный пакет для дистанционного обучения




ПЕРЕДАЧА

ДИСКРЕТНЫХ

СООБЩЕНИЙ

Конспект лекций




Кафедра передачи дискретных

сообщений и телеграфии (ПДС и Т)




Для специальности: 200900

направления 550400


Разработчик:
Кандидат технических наук, доцент

кафедры ПДС и Т
Зюко Владимир Андреевич



Москва 2001


ОГЛАВЛЕНИЕ



Предисловие


. . . . . . . . . . . . . . . .

4

Глава 1.

СИСТЕМЫ ПЕРЕДАЧИ ДИСКРЕТНЫХ СООБЩЕНИЙ . . . . . . . . . . . .


5

1.1.

Основные понятия и определения . . . . . .

5

1.2.

Структурная схема системы ПДС . . . . . .

8

Контрольные вопросы . . . . . . . . . . . . .





14

Глава 2.

ЗАЩИТА ОТ ОШИБОК . . . . . . . . .

15

2.1.

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


15

2.2.

Построение корректирующих кодов . . . . .

16

2.3.

Классификация корректирующих кодов . . . .

18

2.4.

Линейные коды . . . . . . . . . . . .

19

2.5.

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

22

2.6.

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

25

Контрольные вопросы . . . . . . . . . . . . .





28

Глава 3.

УСТРОЙСТВА ПРЕОБРАЗОВАНИЯ СИГНАЛОВ . . . . . . . . . . . . .


29

3.1.

Назначение и классификация устройств преобразования сигналов . . . . . . . . .


29

3.2.

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

30

3.3.

Дискретный канал с частотной модуляцией . .

31

3.4.

Дискретный канал с фазовой модуляцией . . .

33

3.5.

Дискретный канал с относительной фазовой модуляцией . . . . . . . . . . . . .


34

3.6.

Дискретный канал с многопозиционной модуляцией . . . . . . . . . . . . .


35

Контрольные вопросы . . . . . . . . . . . . .





37

Глава 4.

^ СИНХРОНИЗАЦИЯ В СИСТЕМАХ ПДС . . .

38

4.1.

Синхронизация в синхронных и стартстопных системах ПДС . . . . . . . . . . . .


38

4.2.

Поэлементная синхронизация . . . . . . .

39

4.3.

Групповая синхронизация . . . . . . . .

43

Контрольные вопросы . . . . . . . . . . . . .





47

Список литературы . . . . . . . . . . . . . .




48

ПРЕДИСЛОВИЕ


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

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

Для закрепления материала и контроля за его усвоением в каждой главе имеются вопросы.
^

Глава 1. СИСТЕМЫ ПЕРЕДАЧИ ДИСКРЕТНЫХ СООБЩЕНИЙ



1.1. Основные понятия и определения


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

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

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

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


ИС

Канал ПДС

(система ПДС)


ПС




Рис.1.1


Источник дискретных сообщений характеризуется алфавитом передаваемых сообщений A. Пусть объем этого алфавита (число символов алфавита) K, а вероятность выдачи символа aiA (1iK) равна p(ai).

Количество информации в сообщении (символе) определяется в битах - единицах измерения количества информации. Было предложено определять количество информации на одно сообщение ai выражением


I(ai) =.


Среднее количество информации H(A), которое приходится на одно сообщение источника независимых сообщений


.


Определенное таким образом среднее количество информации называется энтропией источника дискретных сообщений. Энтропия максимальна, если символы источника появляются независимо и с одинаковой вероятностью.

Определим энтропию источника сообщений, если K=2 и p(a1)=p(a2)=0,5. Тогда


.


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

Среднее количество информации, выдаваемое источником в единицу времени, называют производительностью источника


H(A)=H(A)/T (бит/с),


где T - среднее время, отведенное на передачу одного символа (сообщения).

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

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


ИС

Преобразователь сообщения в сигнал


Система ПДС

Преобразователь

сигнала в сообщение


ПС




рис.1.2


Различаются два вида дискретных сигналов: дискретный сигнал непрерывного времени и дискретный сигнал дискретного времени.

^ Дискретные сигналы непрерывного времени могут изменяться в произвольные моменты времени, но их величины принимают только разрешенные (дискретные) значения.

^ Дискретные сигналы дискретного времени (сокращенно дискретные) в дискретные моменты времени могут принимать только разрешенные (дискретные) значения.

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

В технике передачи данных такие сигналы называют цифровыми сигналами данных (ЦСД). Рассмотрим далее основные определения, относящиеся к ЦСД.

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

u

Элементы ЦСД


U1


д


б


а


в


г


ж


е


з



t


ЗИ

ЗМ

Рис.1.3

На рис.1.3 изображен ЦСД, информационным параметром которого является амплитуда, а множество возможных значений этого параметра равно двум (u=U1 и u=0).

Часть цифрового сигнала данных, отличающаяся от остальных частей значением одного из своих информационных параметров, называется элементом ЦСД.

Фиксируемое значение состояния информационного параметра сигнала называется значащей позицией. Момент, в который происходит смена значащей позиции сигнала, называется значащим моментом (ЗМ). Интервал времени между двумя соседними значащими моментами сигнала называется значащим интервалом времени (ЗИ).

Минимальный интервал времени которому равны значащие интервалы времени сигнала, называется единичным интервалом (интервал а-б, б-в и другие на рис.1.3).

Элемент сигнала, имеющий длительность, равную единичному интервалу времени, называется единичным элементом (е.э.).

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


^ 1.2. Структурная схема системы ПДС


Структурная схема системы ПДС изображена на рис.1.4. Источник и получатель сообщений вместе с преобразователем сообщения в сигнал в состав системы ПДС не входят.

помеха


от ПС

к ПС


Кодер источника

Кодер канала


УПС

Канал связи


УПС

Декодер канала

Декодер источника




Рис.1.4


Символы aiA от источника дискретных сообщений поступают в виде кодовых комбинаций, которые состоят из единичных элементов. Кодовая комбинация характеризуется основанием кода m и числом единичных элементов, составляющих кодовую комбинацию (длиной кода n), которая отображает передаваемый символ ai. Основание кода характеризует возможное число различных значащих позиций поступающего от ИС сигнала.

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

Используя пятиэлементные комбинации, можно организовать передачу 32 символов. Набор символов, предусмотренный кодом МТК-2, является достаточным для передачи обычных текстов. Для передачи данных требуется использовать больше символов. В связи с этим был разработан семиэлементный код МТК-5.

Коды МТК-2 и МТК-5 в технике ПДС называются первичными кодами.

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

Рассмотрим основные идеи «сжатия» сообщений или, точнее, сокращения избыточности, содержащейся в сообщении. Пусть в течение времени T передается некоторое сообщение, состоящее из N букв. Каждая буква представлена равномерным n – элементным кодом. Идея эффективного кодирования, направленного на снижение избыточности, основывается на использовании неравномерных кодов - кодов, для которых длина кодовой комбинации будет обратно пропорциональна вероятности появления буквы, которую она отображает. При этом средняя длина кодовой комбинации (математическое ожидание количества единичных элементов)


,


где nk - длина k-й кодовой комбинации, pk - вероятность появления в тексте k-й кодовой комбинации; K - алфавит источника или число разновидностей кодовых комбинаций.

Так как n* должно быть меньше n, то время передачи сообщения


T*=n*N<T


а коэффициент сжатия


.


Каковы потенциальные возможности сжимающих устройств? Ответ на этот вопрос дает первая теорема Шеннона, согласно которой при любом способе кодирования всегда выполняется неравенство n*H(A), где H(A) - энтропия сообщения, определяемая выражением


.


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

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

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

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

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

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

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

Д
.
искретный канал характеризуется скоростью передачи информации, измеряемой в битах в секунду (бит/с). Другой характеристикой дискретного канала является скорость модуляции B, измеряемая в Бодах. Она определяется числом единичных элементов, передаваемых в секунду. Скорость модуляции B и скорость передачи информации связаны соотношением R=B I, где I - количество бит информации, которое «несет на себе» один единичный элемент.


Пример 1.1. Рассчитаем скорость модуляции B и скорость передачи информации R в дискретном канале. Длительность единичного элемента возьмем равной мс. Будем считать, что каждый информационный элемент несет один бит информации и на каждые семь информационных элементов приходится один проверочный.

С
.

.
корость модуляции определяется как ^ B=1/ и, следовательно, B=1/0,01=100 Бод. Скорость передачи информации будет определяться числом информационных элементов, переданных в секунду, т.е.

R=B I=100 7/8=87,5 бит/с.

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


Kош=nош/nпер,


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

Для характеристики канала передачи данных используются следующие параметры - коэффициент ошибок по кодовым комбинациям и эффективная скорость передачи информации. Коэффициент ошибок по кодовым комбинациям характеризует верность передачи кодовых комбинаций и определяется отношением числа ошибочно принятых кодовых комбинаций к числу переданных на заданном интервале времени.

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

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

Различают синхронную и асинхронную передачу дискретных сигналов. При синхронной передаче дискретного сигнала его ЗМ находятся в требуемом постоянном фазовом соотношении со значащими моментами любого другого передаваемого сигнала. При асинхронной передаче дискретного сигнала его ЗМ могут находиться в любых фазовых соотношениях со значащими моментами любого другого сигнала.

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

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

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

^ С

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

Т

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

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

Простейшим методом, позволяющим на приеме отделить одну кодовую комбинацию от другой, является введение в состав каждой комбинации специальных элементов в начале и конце комбинации. Элемент, стоящий в начале кодовой комбинации, называется стартовым, а в конце - стоповым. Передаваемая таким образом последовательность называется стартстопной. Рассмотренный метод передачи относится к асинхронным, так как передачу любой кодовой комбинации можно начать в любой момент времени.
^
КОНТРОЛЬНЫЕ ВОПРОСЫ




  1. Дайте определение понятиям «информация», «сообщение», «сигнал».

  2. Как определить энтропию источника независимых сообщений?

  3. Дайте определение понятиям «производительность источника», «скорость передачи информации», «пропускная способность канала».

  4. Какой сигнал называется цифровым сигналом данных (ЦСД)? Что такое информационный параметр, значащий момент, единичный интервал, единичный элемент ЦСД?

  5. Чем отличаются изохронные сигналы от анизохронных?

  6. В чем заключается основная идея эффективного кодирования? Сформулируйте и поясните первую теорему Шеннона.

  7. Приведите структурную схему системы передачи дискретных сообщений.

  8. Поясните определения: дискретный и расширенный канал.

  9. Что такое скорость модуляции?

  10. Какие задачи выполняют устройства поэлементной синхронизации? Какие задачи выполняют устройства групповой синхронизации?
^

Глава 2. ЗАЩИТА ОТ ОШИБОК



2.1. Методы защиты от ошибок в системах без обратной связи


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

Многократная передача кодовых комбинаций является наиболее просто реализуемым способом повышения верности. Пусть передается буква А, число повторений возьмем равным пяти. Если на приемном конце имеем АБААС (буква А исказилась 2 раза, превратившись соответственно в Б и С), то выносится решение о том, что передавалась буква А, поскольку в последовательности из пяти букв она встречалась наиболее часто. Если в принятой последовательности ни одна из букв не повторяется, то принятое сообщение ликвидируется (стирается).

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

При одновременной передаче кодовых комбинаций по нескольким параллельным каналам (обычно число каналов нечетное) решение о том, какая кодовая комбинация передавалась, выносится методом голосования (т.е. так же, как и при многократной передаче кодовых комбинаций).

При передаче сообщений по ^ N параллельным каналам скорость передачи информации не зависит от числа каналов. Однако при этом существенно возрастают (в N раз!) расходы на аренду каналов.

Более эффективно используются дискретные каналы при применении корректирующих кодов. В однонаправленных системах это должны быть коды, исправляющие ошибки. Широкое распространение на практике получили двоичные корректирующие коды, т.е. коды, при формировании которых используются только два типа элементов: 0 и 1. Только такие коды и будут рассматриваться в дальнейшем.

Какие предельные возможности помехоустойчивого кодирования? Ответ на этот вопрос дает вторая теорема Шеннона, согласно которой, если производительность источника дискретных сообщений меньше пропускной способности канала H’(A)<C, то существует способ кодирования и декодирования, при котором в принципе возможна безошибочная передача сообщений. Если же H’(A)>C, то таких способов не существует.


^ 2.2. Построение корректирующих кодов


Каждому символу исходного алфавита сообщений объема Na поставим в соответствие n-элементную двоичную последовательность (кодовую комбинацию). Возможное (общее) число последовательностей длины n составляет N0=2n. Для обнаружения (исправления) на приеме ошибок должно соблюдаться условие Na<N0.

Если Na=N0, то все возможные последовательности n-элементного кода используются для передачи или, как говорят, являются разрешенными. Полученный таким образом код называется простым, т.е. неспособным обнаруживать (исправлять) ошибки.


Пример 2.1. Для передачи сообщений, число которых равно восьми (Na=8), используется трехэлементный код. Число кодовых комбинаций, которое можно при этом получить, N0=23=8. Комбинации, образуемые трехэлементным кодом, сведены в табл. 2.1.


Таблица 2.1


Номер комбинации

0

1

2

3

4

5

6

7

Вид комбинации

000

001

010

011

100

101

110

111



Из таблицы видно, что комбинация под номером 0 отличается от комбинации 1 только в одной позиции. Следовательно, если при передаче комбинации 000 произойдет ошибка в третьем элементе, то получится комбинация 001 (комбинация 1), т.е. произойдет ошибка, которую невозможно ни исправить, ни обнаружить.

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








0

1

0






























1

0

0




























1

1

0 .


Поэтому расстояние Хемминга d=2. Иначе его определяют как вес суммы по модулю два ( - условное обозначение суммы) этих кодовых комбинаций. Весом W кодовой комбинации называется число входящих в нее ненулевых элементов.

Перебрав все возможные пары кодовых комбинаций, можно найти минимальное значение d, которое буем обозначать в дальнейшем d0 и называть кодовым расстоянием. Для примера 2.1 кодовое расстояние d0=1. Рассмотренный в примере код является простым. Любая ошибка (даже одиночная!) при использовании такого кода приведет к тому, что переданная разрешенная кодовая комбинация перейдет в другую разрешенную кодовую комбинацию. Таким образом, простой код не способен обнаруживать и тем более исправлять ошибки и имеет d0=1.

Для того чтобы код мог обнаруживать ошибки, необходимо соблюдение неравенства Na<N0. При этом неиспользуемые n-элементные кодовые комбинации, число которых (N0-Na), будем называть запрещенными. Они определяют избыточность кода. Очевидно, что появление ошибки в кодовой комбинации будет обнаружено, если переданная разрешенная комбинация перейдет в одну из запрещенных. В качестве Nр=Na разрешенных кодовых комбинаций надо выбирать такие, которые максимально отличаются друг от друга.

Пример 2.2. Алфавит передаваемых сообщений Na=2. Выберем из числа комбинаций, представленных в табл. 2.1, две. Очевидно, что ими должны быть комбинации 000, 111 или 001,110 и т.д. Кодовое расстояние d0=3. Ошибки кратности один или два превращают любую разрешенную кодовую комбинацию в запрещенную. Следовательно, максимальная кратность обнаруживаемых таким образом ошибок равна двум (tо.ош=2).

Нетрудно догадаться, что минимальное кодовое расстояние d0 и гарантированно обнаруживаемая кратность ошибок связаны соотношением tо.ош= d0 - 1.

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

Связь между d0 и кратностью исправляемых ошибок определяется выражением tи.ош= (d0/2 - 1) для четного d0 и tи.ош= (d0 - 1)/2 для нечетного d0.


Итак, задача получения кода с заданной корректирующей способностью сводится к задаче выбора (путем перебора) из N0=2n кодовых комбинаций Na комбинаций с требуемым кодовым расстоянием d0. Если n достаточно мало, то такой перебор не представляет особого труда. При больших n перебор может оказаться непосильным даже для современной ЭВМ, поэтому на практике используют методы построения кодов, не требующие перебора с целью получения кода с заданным d0 и отличающиеся невысокой сложностью реализации.


^ 2.3. Классификация корректирующих кодов


Помехоустойчивые или корректирующие коды делятся на блочные и непрерывные. К блочным относятся коды, в которых каждому символу алфавита сообщений соответствует блок (кодовая комбинация) из n(i) элементов, где i - номер сообщения. Если n(i)=n, т.е. длина блока постоянна и не зависит от номера сообщения, то код называется равномерным. Такие коды чаще применяются на практике. Если длина блока зависит от номера сообщения, то блочный код называется неравномерным. В непрерывных кодах передаваемая информационная последовательность не разделяется на блоки, а проверочные элементы размещаются в определенном порядке между информационными. Проверочные элементы в отличие от информационных, относящихся к исходной последовательности, служат для обнаружения и исправления ошибок и формируются по определенным правилам.

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

Разделимые коды делятся на систематические или линейные и несистематические или нелинейные. Линейные коды получили свое название потому, что их проверочные элементы представляют линейные комбинации информационных элементов. Большую и важную подгруппу линейных кодов образуют циклические коды. Линейные коды реализуются наиболее просто, что привело к их широкому использованию в УЗО. Для линейного кода применяется обозначение (n, k) - код, где n - число элементов в комбинации; k - число информационных элементов. Нелинейные коды характеризуются наличием двух или более систем проверок внутри каждой кодовой комбинации. Наиболее часто используются проверки на чётность числа единиц и нулей в разрешенных кодовых комбинациях.


^ 2.4. Линейные коды


Пусть имеется разрешенная кодовая комбинация a1 a2 ... ak b1 b2 ... br линейного (n, k) - кода, где a1 ... ak - множество информационных элементов; b1 ... br - множество проверочных элементов. Как уже указывалось выше, в линейных кодах проверочные элементы являются линейной комбинацией информационных. Значение любого проверочного разряда


.


Коэффициенты cji принимают значения 0 или 1. Таким образом линейный код полностью определяется r k коэффициентами cji ( j=1,2,...,r, i=1,2,...,k).

При построении линейных кодов все разрешенные кодовые комбинации могут быть найдены по нескольким исходным комбинациям, которые записываются в виде производящей матрицы Gn,k , левая часть которой представляет единичную матрицу Ik исходного простого кода, а правая Br,k - матрицу проверочных элементов. Размерность такой матрицы nk, т.е.


G n,k = .


Сокращенно производящую матрицу записывают в виде


Gn,k=| Ik Br,k |.


Минимальный вес разрешенных кодовых комбинаций должен быть не меньше d0. Так как вес каждой строки единичной матрицы W=1, вес каждой строки матрицы проверочных элементов должен быть не меньше d0 - 1, а вес суммы по модулю два двух любых ее строк - не меньше d0 - 2.


Пример 2.3. Построить производящую матрицу линейного кода с d0=3 и k=4.

Пользуясь условием, что при d0=3 , находим r=3 и n=k+r=7. Запишем все возможные строки матрицы Br,k в порядке возрастания соответствующих двоичных чисел: 000; 001; 010; 011; 100; 101; 110; 111. Из этих восьми чисел отберем только те, которые удовлетворяют перечисленным выше условиям для матрицы Br,k .

  1. В каждой строке не менее d0 - 1 единиц: d0 – 1 = 2. Этому условию удовлетворяют комбинации: 011, 101, 110, 111.

  2. Сумма двух любых строк по модулю два должна иметь не меньше d0 - 2 единиц: d0 – 2 = 1. Легко убедиться, что выбранные комбинации удовлетворяют этому требованию, например,







0

1

1







1

0

1







0

1

1





























































1

1

0







1

1

1







1

0

1




и т.д.


























































1

0

1

,




0

1

0

,




1

1

0











Э
.

.

.
ти кодовые комбинации могут быть сопоставлены со строками единичной матрицы в любом порядке. Всего может быть построено k! (4!=1 2 3 4=24) видов производящих матриц. Располагая эти комбинации в порядке возрастания двоичных чисел, получим матрицу Br,k :





0

1

1


B3,4=

.



1

0

1




1

1

0




1

1

1




b1

b2

b3


Объединяя I4 и B3,4 , получим производящую матрицу линейного кода (7,4):





1

0

0

0

0

1

1


.

G7,4=

.



0

1

0

0

1

0

1




0

0

1

0

1

1

0




0

0

0

1

1

1

1




a1

a2

a3

a4

b1

b2

b3
  1   2   3   4   5



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

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

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