Передача информации. Структурная схема передачи информации от источника к приемнику через канал связи



Скачать 392.98 Kb.
страница1/4
Дата30.12.2012
Размер392.98 Kb.
ТипДокументы
  1   2   3   4
Теория информации и кодирования



  1. Информационная модель канала связи с помехами.


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

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


  1. Принципы построения корректирующих кодов.


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

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

мала.

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

больше пропускной способности канала.
Если через канал связи без помех передается последовательность дискретных сообщений длительностью T , то скорость передачи информации по каналу связи
(бит / сек) = lim ( I / T )

T → ∞

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

Пропускная способность – максимальное количество данных, которое можно передать по каналу связи за 1 секунду.

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


Общее количество кодовых комбинаций в коде обычно меньше, чем количество всех возможных

комбинаций из данного набора символов.
равномерные

Коды

неравномерные
В равномерных кодах все комбинации содержат одинаковое количество символов (разрядов).

В неравномерных кодах каждая комбинация содержит различное количество разрядов (например,

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

В вычислительной технике используют избыточные коды, т.е. в самом коде присутствует только часть комбинации из всех возможных. Эти комбинации – разрешенные, остальные – запрещенные. Если при передаче информации кодовое слово попало в запрещенную область, то фиксируется факт наличия ошибки. Очевидно, что разрешенные комбинации должны отличаться между собой не менее, чем 2-мя разрядам.
Пример : Пусть передаются числа от 0 до 7. Закодируем их следующим образом :


Десятичное число

Двоичное число

0

1

2

3

4

5

6

7

0000

0011

0101

0110

1001

1010

1100

1111



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


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




1101 позволяет обнаруживать одиночные, двоичные и троичные ошибки

0010

  1. Обнаруживающая и корректирующая способности кодов.



Будем считать, что любая передаваемая кодовая комбинация Bi , i = 1,2,…,N вследствие действия помех может перейти в другую кодовую комбинацию Bj , j = 1,2,…,N0




B1 B1




B2 B2

. .

. .

. .

BN BN0
Общее количество переходов из разрешенной области (от источника) к приемнику Q = N * N. Среди этих переходов можно выделить 3 варианта перехода :


  1. Без искажений (количество таких переходов N = 2 m)

  2. Каждая разрешенная комбинация может перейти в другие разрешенные N*(N-1) = 2 m (2 m -1).

Эти ошибки не могут быть обнаружены.

  1. Разрешенные комбинации переходят в запрещенные и могут быть обнаружены. N*(N0 - N)


Следовательно, обнаруживающая способность может быть определена как доля :
N*(N0 - N) / N*N0 = 1 – N/ N0 = 1 – 2 m / 2 n = 1 – 1 / 2 K
Для коррекции ошибок необходимо множество всех запрещенных комбинаций разбить на М взаимно непересекающихся подмножеств и каждому такому подмножеству поставить в однозначное соответствие 1 разрешенную комбинацию Bi. Если при передаче информации искаженное слово попало в подмножество Ni, то будет считаться, что правильное слово Bi.

Корректирующая способность равна отношению всех комбинаций, которые могут быть скорректированы ко всем, которые могут быть обнаружены :
(N0 - N) / N*(N0 - N) = 1 / N = 1 / 2 m
Рассмотрим следующий пример, который покажет каким образом можно скорректировать одиночную ошибку при передаче информационной части числа состоящего из одного разряда.

m = a1 = { 0,1 }. Введем дополнительные разряды а2 и а3



a1


a2


a3




1

1

0

рареш.

0

1

1

1

0

1

0

0

1

запрещ.

0

0

1

разреш.

1

0

0

0

1

0

1

1

0

запрещ.



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

  1. Построение кодов с учетом статистики помех.


Введем понятие вектора (последовательности) ошибок.
1011010 - искаженное слово



1001110 - неискаженное слово

0010100 - последовательность ошибок
Любое искаженное слово чисто теоретически можно представить в виде суммы по модулю 2 двух последовательностей данных - неискаженного слова и последовательности ошибок. В последовательности ошибок стоят все нули, кроме разрядов, в которых ошибка, причем неважно какая это ошибка ( с 1 на 0 или с 0 на 1 ).
Пример : Пусть код состоит из разрешенных комбинаций В1 = 001, В2 = 011, В3 = 110.



Вектор ошибок

Кодовая комбинация

Кратность

ошибок Q

В1 = 001

В2 = 011

В3 = 110

000

001

011

110

0

001

010

100

001

( 011 )

101

010

( 001 )

111

111

100

010

1

011

101

110

010

100

111

000

( 110 )

101

101

( 011 )

000

2

111

( 110 )

100

( 001 )

3



Как видно из таблицы из 21 возможной ошибки 6 не могут быть обнаружены ( они указаны в скобках ).

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

Рассмотрим варианты построения подмножеств для коррекции одиночной ошибки :


  1. М1 = { 000, 101 } 2) М1 = { 000, 101 } 3) М1 = { 000, 101 }

M2 = { 010, 111 } M2 = { 010} M2 = { 111 }

M3 = { 100 } M3 = { 100, 111 } M3 = { 100, 010 }

  1. Классификация кодов.



Корректирующие коды можно разделить на 2 класса :


  1. Блочные (блоковые)

  2. Непрерывные


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


  • равномерные коды

  • неравномерные коды


Блочные коды бывают:


  • систематические (разделимые)

  • несистематические (неразделимые)


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

Они обозначаются (n,m) , n – длина кодовой комбинации , m – информационная часть.

К несистематическим относят коды , разряды которых нельзя разделить на информационные и контрольные.

Систематические коды разделяют на :


  • линейные

  • нелинейные


К линейным относят такие коды, поразрядная сумма по модулю 2 (в общем случае по модулю q ) любых двух кодовых слов также является кодовым словом (разрешенным). Линейные блоковые коды часто называют групповыми. Примером нелинейного кода является код Бергера, у которого контрольные разряды представляют двоичную запись числа единиц в последовательности информационных разрядов.

Непрерывные коды характеризуются тем, что операция кодирования / декодирования производится над непрерывной информационной последовательностью без разбиения её на блоки.

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


  1. Основные характеристики блочных кодов.


Корректирующая способность - способность кода обнаруживать и исправлять ошибки.
К основным характеристикам относится :
1) n – длина кода

2) m – информационная часть числа

3) k – контрольные разряды

4) М – основание кода ( для двоичных : 2 )

5) N = 2 m – мощность кода ( количество разрешенных комбинаций)

6) N0 - общее количество всех комбинаций

7) Избыточность кода

8) W – вес кодовой комбинации

9) d min – минимальное кодовое расстояние


λ = k / n – избыточность
Корректирующая способность кода зависит от избыточности и от того, где стоят контрольные разряды.

  1. Понятие минимального кодового расстояния.



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

n

d ( Bi , Bj ) = ∑ ( bi,k bj,k )

k=1
Под минимальным кодовым расстоянием d min понимается наименьшее кодовое расстояние рассматриваемое между всеми возможными парами в коде.
1) d min >= t + 1 - для обнаружения t ошибок

2) d min >= 2t + 1 - для коррекции t ошибок

3) d min >= t + s + 1 , s < t - для обнаружения t ошибок и коррекции s ошибок
Как видно корректирующая способность непосредственно связана с d min. Она обеспечивается введением избыточных контрольных разрядов, при этом очевидно, что их количество нужно выбирать минимальным. Код имеющий минимальное количество контрольных разрядов называется оптимальным.

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


  1. граница Хэмминга

(d min -1 )/ 2

k >= log 2 ( 1 + ∑ c in ) , c mn = n ! / m! ( n – m! )

i=1



  1. граница Плоткина


k >= 2 ( d min -1 ) – log 2 d min


  1. граница Вартамова-Гильберта


(d min -1 )/ 2

k >= log 2 ( 1 - ∑ c in )

i=1
Граница Хэмминга близка к оптимальной границе для кодов с большим m / n ( m / n >= 1 / 2 ) , т.е. для высокоскоростных кодов, а граница Плоткина для низкоскоростных ( m / n <= 1 / 3)

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

Таким образом, границы 1 и 2 являются необходимым условием существования кода, а 3 – достаточным. Равенство в выражении 3 справедливо для совершенных кодов. Эти коды исправляют все ошибки кратности <= ( d min - 1) / 2 и не исправляют ни одной ошибки большей кратности.

Код Хэмминга – совершенный код.


  1. Коды Хэмминга ( кодирование информации ).


Это я знаю

  1. Коды Хэмминга ( декодирование информации ).
  1   2   3   4

Похожие:

Передача информации. Структурная схема передачи информации от источника к приемнику через канал связи iconСтруктурная схема (обобщенная) передачи информации от источника к приемнику 2
Эта операция называется кодированием. После прохождения информации через канал связи к приемнику ее необходимо восстановить, то есть...
Передача информации. Структурная схема передачи информации от источника к приемнику через канал связи iconИсточник и получатель, а сама информация передается по каналу связи
Процесс передачи информации, источник и приемник информации, канал передачи информации. Скорость передачи информации
Передача информации. Структурная схема передачи информации от источника к приемнику через канал связи iconБилет №5 Процесс передачи информации, источник и приемник информации, канал передачи информации. Скорость передачи информации
Процесс передачи информации, источник и приемник информации, канал передачи информации. Скорость передачи информации
Передача информации. Структурная схема передачи информации от источника к приемнику через канал связи icon1. Процесс передачи информации, источник и приемник информации, канал передачи информации. Скорость передачи информации
Процесс передачи информации, источник и приемник информации, канал передачи информации. Скорость передачи информации
Передача информации. Структурная схема передачи информации от источника к приемнику через канал связи iconЛекция №5 По дисциплине Теория информации
Согласование пропускной способности канала передачи информации с потоком информации от источника
Передача информации. Структурная схема передачи информации от источника к приемнику через канал связи iconКлассификация сетей связи
Сети связи – совокупность технических средств, предназначенных для передачи информации на расстояние от источника до потребителя
Передача информации. Структурная схема передачи информации от источника к приемнику через канал связи iconПередача информации. Соло на клавиатуре
Цель урока: дать учащимся представление об информационном процессе передачи информации
Передача информации. Структурная схема передачи информации от источника к приемнику через канал связи iconДоклад «О конкуренции между услугами связи для целей передачи голосовой информации по сетям фиксированной телефонной связи и подвижной радиотелефонной связи»
На основе анализа рынка услуг телефонной связи для целей передачи голосовой информации, в результате которого установлено, что функционально...
Передача информации. Структурная схема передачи информации от источника к приемнику через канал связи iconПрограмма курса «Теория информации и кодирования»
Понятие информации, энтропии. Системы связи. Дискретные источники. Описание источника при помощи случайного процесса. Статистическая...
Передача информации. Структурная схема передачи информации от источника к приемнику через канал связи iconПонятие информации. Виды информации. Роль информации в живой природе и в жизни людей. Язык как способ представления информации: естественные и формальные языки. Основные информационные процессы: хранение, передача и обработка информации
Начает сведение, разъяснение, ознакомление. Понятие «информация» является базовым в курсе информатики, невозможно дать его определение...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org