1. Визначення електронної системи(ЕС). Ціль побудови ес. Структура ес. Класи ес. Слово система (англ system) походить від грецького складений

• Название: 1. Визначення електронної системи(ЕС). Ціль побудови ес. Структура ес. Класи ес. Слово система (англ system) походить від грецького складений
• Анкор: denbnovetsky.pdf
• Дата: 11.08.2018
• Размер: 2.18 Mb.
• Имя файла: denbnovetsky.pdf
• Тип: Документы; #22798
• страница: 6 из 7

Код Хаффмена
Обеспечивает однозначность построения кода со средним числом символов на буквы для данного распределения вероятности символов. Построение: буквы алфавита записываются в порядке уменьшения вероятности, 2 последние буквы с наименьшей вероятностью обьединяются в одну самостоятельную группу с большей вероятностью. сравниваются вероятности с учетом, что 2 последних буквы уже в группе с сумарной вероятностью и процесс повторяется снова. Процесс повторяется снова до тех пор пока не получится единственная группа с вероятностью 1. Потом строится кодовое дерево на базеполученных данных, причем ветви с большей вероятностью присваивается значение
1, а ветви с меньшей 0. ответвление продолжается до момента достижения вероятности каждого сообщения.
Рефлексный код (Грея)
Строение кода Грея
Код Грея - непозиционный код с одним набором символов (0 и 1) для каждого разряда.
Таким образом, в отличие от римской системы счисления число в коде Грея не является суммой цифр. Чтобы показать соответствие последовательности чисел коду Грея можно воспользоваться таблицей, но есть и наглядное правило построения этой последовательности.
Младший разряд в последовательности чисел в коде Грея принимает значения 0 и 1, затем следующий старший разряд становится единичным и младший разряд принимает свои значения уже в обратном порядке (1, 0). Этим и объясняется название кода -
"отражѐнный". Соответственно, два младших разряда принимают значения 00, 01, 11, 10, а затем, при единичном следующем старшем разряде, те же значения в обратном порядке
(10, 11, 01, 00). Ниже дана таблица, показывающая первые восемь чисел в двоичном коде и в коде Грея.
N двоичный код код Грея N двоичный код код Грея
0 000 000 4
100 110

1 001 001 5
101 111 2
010 011 6
110 101 3
011 010 7
111 100
Использование кода Грея
Благодаря своему основному свойству (отличие соседних чисел только в одном разряде) код Грея применяется, например, в построенных на кодовых дисках определителях углового положения вала. В оптическом кодовом диске единицы и нули кодируются прозрачными и непрозрачными областями. С одной стороны диск просвечивается ориентированной вдоль его радиуса световой щелью, с другой стороны размещаются фотодиоды. Считываемый с фотодиодов двоичный код и указывает угол поворота диска.
Ниже показаны 3-разрядные диски на позиционном коде и коде Грея (в силу ограниченности выразительных средств диски "разрезаны" посредине последнего угла и "вытянуты" в ленту, как это делается и для карт земного шара): позиционный код код Грея
Недостаток кодирования позиционным двоичным кодом заключается в том, что при смене нечѐтного кода чѐтным считанный с фотодиода код может оказаться неверным.
Характеристики фотодиодов обычно не идентичны и при смене сразу нескольких разрядов выходные уровни фотодиодов могут измениться не строго одновременно.
Например, при переходе от третьего угла к четвѐртому или от седьмого угла к нулевому меняются все разряды и какое-то время на выходе фотодиодов можно получить любое значение от 0 до 7. В коде же Грея при переходах ошибка не будет превышать один угол.
Манчестерский код.
Каждий разряд исходного двоичного кода записывается в виде двух елементов
0 01 1
10


Например исходной кодовой комбинации 0010011 соответствует комбинация
01011001011010
Приемное устройство, которое состоит из двух соединенных элементов Манчестерского кода должно фиксировать переход 0 в 1 или 1 в 0, в случае приема двух нулей или единиц, приемник фиксирует ошибку. Переход полярности происходит строго в центре каждого временного интервала, что очень удобно для синхронизации, но есть отрицательная сторона: Манчестерский код требует удвоения скорости линейного кодирования.
Обнаруживает ошибки любой кратности, но не обнаруживает зеркальные ошибки, когда соседние элементы одного такта под влиянием помех меняются на противоположные.
Избыточность кода:
1 1
2 2
изб
k
R
k
 

Преимущества:

Отсутствие постоянной составляющей при передаче комбинации по каналу связи

Возможность самосинхронизации генератора приемника, так как прием каждого бита информации осуществляется по переднему фронту, который фиксируется в центре бита.

36. Цілі, параметри та принципи перешкодостійкого кодування. Переваги та
недоліки
Под помехоустойчивыми кодами понимают коды, позволяющие обнаруживать или обнаруживать и исправлять ошибки, возникающие в результате влияния помех .
Помехоустойчивость кодир обеспечивается за счет введения избыточности в кодовые комбинации, тоесть за счет того, что не все символы в кодовой комбинации использ для передачи информации. Помехоустойчтвые коды-это одно из наиболее эффект средств для обеспечения высокой помехоустойчивости и высокой верности. Помехоустойчивое кодиров должно осущ так, что бы сигнал соотв принятой послед символов после воздействия на него помехи оставался ближе к сигналу соотв перед послед символов.
Проверка на приемной стороне дает возможность обнаружить и исправить ошибки.
Основной задачей помехоустойчивого кодирования является решение проблемы обеспечения высокой достоверности передаваемых данных за счет применения устройств кодирования/декодирования в составе системы передачи цифровой информации, структурная схема которой представлена на рис. 1.1. Данная схема широко используется в теории помехоустойчивого кодирования, поскольку она охватывает большинство ситуаций, которые встречаются на практике.
Идея может быть рассмотрена на примере двоичного кода, тоесть m=2. Количество разрядов n в кодовой комбинации принято называть длина или значность кода.Символы каждого разряда могут принимать значения 0 или 1 при этом количество единиц кодовой комбинации называется весом кодовой комбинации ω.
Например, 11000111101 n=11, ω=7. Степень отличия любых двух кодовых комбинаций данного кода характеризуется кодовым расстоянием d оно выражается числом позиций или символом, в которых комбинации отличаются одна от другой и определяется как вес суммы по модулю этих кодовых комбинаций.
11000111101
+
10111000101
=
01110110111 d=7
Полученая в результате суммирования новая кодовая комбинация вследствии расстоянию между исходной кодовой комбинации равно 7.

∑
Геометрическая интерпритация. Допустим имеется алфавит из 3 символов: 000, 001, 010,
011,100,101,111.
Ошибку можно обнаружисть если кодовые комбинации отстают на два ребра 000,
011,101,110. Для данного кода для исправления ошибки необходимо чтобы отличалось на
3 ребра. Ошибки вследствии воздействия помех проявляются в том , что в одном или нескольких разрядах нули переходят в единицы. В результате создается ложная комбинация.Если ошибки происходят только в одном разряде, то их название однократные. При наличии ошибок в двух-трех разрядах-двукратные, трѐхкратные.
Эксперементирование исследования каналов связи показали что ошибки символов при передачи по каналам связи групируются в пачки. Под пачкой ошибок понимают участок последовательности, начинающийся и заканчивающейся ошибочно принятыми символами. Внутри пачки могут быть правильно принятые сиволы но вся пачка бракуется.
Для указания мест кодовой комбинации, где имеется искажение символов используются вектор ошибок(e).Ветор ошибки n-разрядного кода -это n раздная комбинации единицы в которой указываю положение искаженных символов. Вектор ошибки характеризует кратность ошибки.
Величина d называется расстоянием – это расстояние всегда целое число, равное числу разрядов, которые отл. Двоичным числам-эти расстояния соответствуют пространству. В более общем случае пространство будет иметь ни 3 координаты, а n-координат и будет отображаться n-мерным кубом.
Если для 5-ти разрядного кода е=01100, то это значит что в 3 и 4 кодовых комбинациях вес вектора ошибки
Ω характеризует кратность ошибки .Сумма по модулю 2 для искаженной кодовой комбинации и вектора ошибки даст исходную неискаженную комбинацию, таким образом помехоустойчивое кодирование обеспечивается за счет введения избыточности кодовой комбинации. Это значит что из n-символов для передачи информации используется только k-символов.(n>k).
Следовательно из числа возможных кодовых комбинаций
.В соответствии с этим все множество возможных кодовых комбинаций разбивается на 2 группы.В первую группу входит множество
. Вторая группа включает в себя
- запрещенная кодовая комбинация.если на приемной стороне установлено , что принятая комбинация относится к группе разреш. то считается, что сигнал прошѐл через канал без искажений.

Параметры помехоустойчивого кода
1.
Длина, значность, число разрядов, разрядность (одно и тоже). n=k+r
2.
Количество информационных, иначе разрешенных символов элементов k, обеспечивающих кодирование передаваемой информации.
3.
Кол-во избыточных, проверочных, контрольных корректирующих, запрещенных
(одно и тоже) r=n-k
Обеспечивает помехоустойчивость кода при наличии помех.
4.
Основание кода. nq=n=M
Кол-во используют при кодировании упорядоченных знаков.
5.
Для сверточного кода используется 3 числа: n,k,K.
6.
Общее число кодовых комбинаций или число всех возможных комбинаций или объем алфавита кода N
0
=q n
=m n
Для двоичных кодов q=m=2.
7.
Вес кода и вес кодовой комбинации для 2-го числа равен 2.
8.
Мощность N
разр
– это число разрешенных кодовых комбинаций.
9.
Избыточность корректирующего кода используется для передачи сообщения w
kk
=r/n=(n-1)/n=1-k/n показывает какую часть от числа символов составляет k. Величина k/n характеризует относительную скорость передачи информации.
10.
Корректирующая способность кода связана с минимальным необходимой избыточностью. Определены верхние и нижние границы для кодов, которые устанавливают связь между максимально возможным кодовым расстоянием корректирующего кода и его избыточности.
Нижняя граница Варшамова r/n=1-(k/n)>=H(d min
-2), где H(x)=-x log
2
(1-x) r>=nH(d min
-2)/(n-1) k/n<=(1- H(d min
-2)/(n-1))/
Позволяет оценить необходимое количество проверочных символов и относительной скорости передачи.
11.
Относительная скорость передачи информации характеризует степень использования избыточности.
R
отн
=k/n
12.
Кратность ошибки.
13.
Кодовое расстояние.
14.
Помехоустойчивость характеризует его способность обеспечивать правильную передачу сообщения в условиях возбуждения помех, поэтому для количественной оценки помехоустойчивого кода млжна использовать вероятность правильного приема: Р
пр
=1-Р
ош
Более удобным критерием оценки помехоустойчивого кода является S=log(1/ Р
ош
).
15.
Эффективность действия помехоустойчивого кода оценивается по след. формуле:
K
KK
=(10lg(E
1
/N
0
*
)/E
1
/N
0
) дБ
E
1
– энергия затраченная на передачу информации в 1 бит.
N
0
– мощность шума на 1 Гц полосы частот канала связи.
E
1
/N
0
*
- отношение этих же величин, но при использовании корректирующего кода.
K
KK
– показывает на сколько применение корректирующего кода позволяет улучшить отнощение сигнал/шум в каналах, сохранение числа ошибок на прежнем уровне.
Значение находится в пределах 3-7 дБ и возрастает при уменьшении числа ошибок.

37. Класифікація перешкодостійких кодів. Коди з подвоєнням кількості елементів.
Інверсний код.
Под помехоустойчивыми кодами понимают коды, позволяющие обнаруживать или обнаруживать и исправлять ошибки, возникающие в результате влияния помех .
Помехоустойчивость кодир обеспечивается за счет введения избыточности в кодовые комбинации, тоесть за счет того, что не все символы в кодовой комбинации использ для передачи информации. Помехоустойчтвые коды-это одно из наиболее эффект средств для обеспечения высокой помехоустойчивости и высокой верности. Помехоустойчивое кодиров должно осущ так, что бы сигнал соотв принятой послед символов после воздействия на него помехи оставался ближе к сигналу соотв перед послед символов.
Проверка на приемной стороне дает возможность обнаружить и исправить ошибки.
Інверсний код.
Кодовые слова инверсного корректирующего кода образуются повторением исходного кодового слова. Если число единиц в исходном слове четное, оно повторяется в неизменном виде; если число единиц нечетное, то при повторении все символы исходного кодового слова инвертируются (нули заменяются единицами, а единицы - нулями).
Например
01010 0101001010 01110 0111010001


Для обнаружения ошибок в кодовом слове, состоящем из символов производится две операции.
Суммируются единицы, содержащиеся в первых k символах кодового слова.
r
k
n



2. Если число единиц четное, последующих символов сравниваются попарно с первыми k символами; если число единиц в первых символах нечетное, последующие символы перед сравниванием инвертируются.
Несовпадение хотя бы одной из пар сравниваемых кодовых символов указывает на наличие ошибки в кодовом слове. Ошибка в кодовом слове не обнаруживается, если одновременно искажается четное число символов в исходном слове и соответствующие им кодовые символы в последовательности повторяемых символов.Инверсный код обладает максимальной помехоустойчивостью.
Избыточность кода:
1 1
2 2
изб
k
R
k
 

Корреляционный код (Код с удвоением).
Элементыданногокодазаменяютсядвумя символами, единица ‘1’ преобразуется в 10, а ноль ‘0’ в 01.
Вместокомбинации 1010011 передается 10011001011010. Ошибкаобнаруживается в том случае, если в парныхэлементахбудутодинаковыесимволы 00 или 11 (вместо 01 и 10).
Например, при k=5, n=10 и вероятностиошибки , . Но при этомизбыточностьбудетсоставлять 50%.
38. Код Хемінга, його побудова: класична, матрична. Реалізація, застосування,
різновиди.
Известно несколько разновидностей кода Хэмминга, характеризуемых различной корректирующей способностью. К этим кодам обычно относят коды с исправлением однократных ошибок и коды с исправлением однократных и обнаружением двукратных ошибок.
Код Хэмминга, обеспечивающий исправление всех однократных ошибок, должен иметь минимальное кодовое расстояние dmin = 3. Длина кода n выбирается из условия где k — количество информационных сигналов.
Код строится таким образом, чтобы в результате p = n — k проверок получить р-разрядное двоичное число, указывающее номер искаженной позиции кодовой комбинации. Для этого проверочные символы должны находиться на номерах позиций, которые выражаются степенью двойки (2 0
, 2 1
, 2 2
,..., 2
р-1
) так как каждый из них входит только в одно из проверочных уравнений. Таким образом, если нумеровать позиции слева направо, то контрольные символы должны находиться на первой, второй, четвертой и т. д. позициях.
Результат первой проверки дает цифру младшего разряда синдрома в двоичной записи.
Если результат этой проверки даст 1, то один из символов проверенной группы искажен.
Таким образом, первой проверкой должны быть охвачены символы с номерами,
r
r

содержащими в двоичной записи единицы в первом разряде: 1, 3, 5, 7, 9 и т. д. Результат второй проверки дает цифру второго разряда синдрома. Следовательно, второй проверкой должны быть охвачены символы с номерами, содержащими в двоичной записи единицы во втором разряде: 2, 3, 6, 7, 10 и т. д.
Аналогично при третьей проверке должны проверяться символы, номера которых в двоичной записи содержат единицы в третьем разряде: 4, 5, 6, 7, 12 и т. д.
Таким образом, проверочные группы должны иметь вид
Проверочная матрица кода должна иметь n столбцов и р строк. Каждый столбец должен составлять двоичную комбинацию, указывающую номер соответствующей позиции кода.
Например, для кода длиной n = 9, обеспечивающего исправление однократных ошибок, количество избыточных символов р = 4. При этом в качестве проверочной может быть выбрана следующая матрица:
Представим в качестве примера простую двоичную комбинацию 10011 кодом Хэмминга.
Так как информационными должны быть третий, пятый, шестой, седьмой и девятый символы, то для рассматриваемого кода а
3
= 1; а
5
= 0; а
6
= 0; а
7
= 1; а
9
= 1. Из условия обеспечения четности сумм получим следующие значения проверочных символов: а
1
= 1; а
2
= 0; a
4
= 1; а
8
= 1. Следовательно, простому пятиэлементному коду 11011 соответствует девятиэлементный код Хэмминга 101100111.
Пусть теперь при передаче произошло искажение пятого символа, т. е. код принял вид
101110111. Тогда в результате первой проверки получим 1, второй — 0, третьей — 1 и четвертой — 0. Таким образом, в результате проверок получен синдром 0101, указывающий на искажение пятого символа. Исправление ошибки сводится к инвертированию символа на пятой позиции.
Код Хэмминга с кодовым расстоянием dmin = 4 получается путем добавления к коду
Хэмминга с dmin = 3 проверочного символа, представляющего собой результат суммирования по модулю два всех символов кодовой комбинации.
Операция декодирования состоит из двух этапов. На первом определяется синдром, соответствующий коду c dmin = 3, на втором — проверяется последнее проверочное соотношение.

Для рассмотренного ранее кода с dmin= 4 проверочная матрица может иметь вид
Дополнительное проверочное соотношение, вводимое для увеличения минимального расстояния кода Хэмминга до dmin = 4, имеет вид
S
5
= a
1
+ a
2
+ a
3
+ a
4
+ a
5
+ a
6
+ a
7
+ a
8
+ a
9
+ a
10
Избыточность кода Хэмминга Kизб = p/n зависит от количества информационных символов и при изменении k от 4 до 1013 изменяется от 0,429 до 0,098 при dmin = 3 и от
0,5 где 0,0107 при dmin = 4.
Код Хэмминга представляет собой блочный код, который позволяет выявить и исправить ошибочно переданный бит в пределах переданного блока.

с кодовым расстоянием
d

3, исправляет одиночные ошибки;

с кодовым расстоянием
d

4 , исправляет одиночные и обнаруживает двойные ошибки.
Проверочные символы кода Хэмминга, как и других систематических кодов, вычисляются путем сложения по модулю два информационных символов, расположенных в определенных разрядах кодового слова. При декодировании эти информационные символы вместе с соответствующим проверочным символом .должны удовлетворять проверке на четность (сумма этих символов по модулю два должна равняться нулю).
Кроме этого общего требования, для кодов Хэмминга является обязательным, чтобы результат проверок на четность при декодировании искаженного кодового слова указывал также номер разряда, в котором расположен искаженный символ.
Пример:
Кількість переданої інформації k=6, кількість контрольних розрядів r=4, тоді довжина кодової комбінації n=r+k=10. Залежність між k інформаційними символами коду, r контрольними символами та n – загальною довжиною коду:
2 2 / (1
)
k
n
n
k

 
, або
2 1
1
r
n
k
r
    
.Для нашого випадку
4 2
11

що є вірно.
Нехай передати треба число 25 (011001), тоді передаваємий код:
10 9 8 7 6 5 4 3 2 1 0
1 * 1 0 0 * 1 * *
,де * - позиції контрольних бітів, які відповідають степеням двійки.
Знайдемо контрольну суму за допомогою операції виключаючого АБО(сума по модулю два) над кодами позицій ненульових бітів:
9 1
0 0
1 7
0 1
1 1
3 0
0 1
1


1 1
0 1
Приклад операції виключаючого АБО:
0011 0101 0110
Підставивши отримані значення замість зірок, отримаємо код Хемінга для передачі коду
011001:
10 9 8 7 6 5 4 3 2 1

0 1 1 1 0 0 1 1 0 1
Перевіримо правильність коду. Для цього знову найдемо суму за допомогою операції виключаючого АБО над кодами позицій ненульових бітів:
9 1
0 0
1 8
1 0
0 0
7 0
1 1
1 4
0 1
0 0
3 0
0 1
1 1
0 0
0 1


0 0
0 0
При сумуванні отримали нулі, отже код складено вірно.
Тепер будемо вважати, що при передачі коду Хемінга 0111001101 перешкода спотворила один із символів, внаслідок чого був прийнятий код 0111011101, який має спотворення у п’ятому розряді, відраховуючи справа.
10 9 8 7 6 5 4 3 2 1 0
1 1 1 0 1 1 1 0 1
Перевіримо прийнятий код: Для цього знову найдемо суму за допомогою операції виключаючого АБО над кодами позицій ненульових бітів:
9 1
0 0
1 8
1 0
0 0
7 0
1 1
1 5
0 1
0 1
4 0
1 0
0 3
0 0
1 1
1 0
0 0
1


0 1
0 1
Ми отримали код адреси помилки: 0101 2
=2 2
+2 0
=5 10
. Це свідчить про те, що спотворення відбулося в п’ятому символі відраховуючи справа. Тому помилковий символ
1 треба виправити на 0.