Шпоры к зачету по Теории информации для заочников 2 курс БТЭУПК - файл n1.doc

приобрести
Шпоры к зачету по Теории информации для заочников 2 курс БТЭУПК
скачать (389.5 kb.)
Доступные файлы (1):
n1.doc390kb.01.06.2012 13:13скачать
Победи орков

Доступно в Google Play

n1.doc

Предмет теории информации.

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

-«надежную» — в процессе передачи не должно происходить потери информации;

-«эффективную» —передача должна осуществляться наиболее быстрым способом;

-помехи присутствуют в любой реальной линии связи.

Решение этой задачи ведется по двум направлениям:

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

*математическое — основывается на теории случайных событий и связано с возможностью ее количественного измерения.

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

Информация (лат. Informatio) — сведения, разъяснения, изложение.

В зависимости от области знания существуют различные подходы к определению понятия информации:

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

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

*в теории информации — сведения, которые снимают полностью или уменьшают существующую до их получения неопределенность.

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

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

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

Выделяют два типа сигналов: непрерывные и дискретные.

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



Рис. 1. Непрерывные (а) и дискретные (б) сигналы. Z - значение параметра сигнала, t- время.

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

Множество знаков, используемых для представления дискретной информации, называется набором знаков. Алфавитом называется набор знаков, в котором установлен порядок их следования. Порядок между знаками устанавливаются с помощью отношения «больше-меньше». Пример алфавита: арабские цифры 0,1...9. Если к этому алфавиту добавить знаки «+», «-», «.» и «,», то сформируется набор знаков, в котором не определен порядок следования знаков.

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

Знаки, используемые для обозначения фонем человеческого языка, называются буквами, а их совокупность - алфавитом языка.

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



Преобразование типа N1N2. Примером устройств являются микрофон; магнитофон и видеомагнитофон; телекамера; радио- и телевизионный приемник. Преобразование N1N2 всегда сопровождается частичной потерей информации. Потери связаны с внешними помехами и помехами, которые производит само информационное техническое устройство. В ряде устройств искажение происходит в силу особенностей преобразования в них сообщения, например, в черно-белом телевидении теряется цвет изображения; телефон пропускает звук в более узком частотном интервале, чем интервал человеческого голоса.

Преобразование типа ND и DN. Перевод ND означает замену описывающей его непрерывной функции Z(t) на некотором отрезке [t1, t2] конечным множеством {Zi, ti} (i = 0...n, где n- количество точек разбиения временного интервала). Согласно теореме Котельникова преобразование ND и DN, может осуществляться без потери информации.
Теорема отсчетов (В. А.Котельникова):

Непрерывный сигнал можно полностью

отобразить и точно воссоздать по

последовательности измерений или

отсчетов величины этого сигнала через

одинаковые интервалы времени, меньшие

или равные половине периода

максимальной частоты, имеющейся в

сигнале.


1.2. Дискретизация непрерывного сигнала. Z - шаг квантования, t - развертка по времени

Преобразование типа D1D2 состоит в переходе при представлении сигналов от одного алфавита к другому - такая операция носит название перекодировка и может осуществляться без потерь.

Энтропия как мера неопределенности

Количественная мера информации необходима для сравнения различных источников сообщений и каналов связей. При введении меры информации абстрагируемся от конкретного смысла информации.

При ожидании сообщения существует неизвестность или неопределенность относительно того, что содержится в ожидаемом сообщении. Сообщение уничтожает эту неопределенность. Значит, чем больше ликвидируется неопределенности, тем большее количество информации несет сигнал. Степень неопределенности различна для разных ситуаций.
Пример 2.1. В шахматы будут играть два игрока. Один из них – белыми фигурами, другой – черными. Неопределенность – кто начнет игру. В данном случае возможны два исхода с равной вероятностью 1/2: игроком будет вынута белая фигура, либо - черная. Значит, неопределенность одинакова для обоих исходов, а значит, и количество информации тоже будет одинаковым.

Пример 2.2. На 32 карточках написано по одной букве русского алфавита. Вынимают одну карточку. Вынутой может оказаться любая карточка с вероятностью 1/32. Уничтоженная неопределенность – какая буква окажется на карточке, большая по сравнению с предыдущим примером, т.к. возможны 32 случая (состояния сигнала). Но на сколько большая, пока ответить невозможно.
Энтропия является мерой неопределенности опыта, в котором проявляются случайные события и равна средней неопределенности всех возможных его исходов.

Энтропия позволяет сравнивать количества информации, приносимые различными сигналами. За единицу измерения принимается неопределенность, содержащаяся в опыте, имеющем лишь два равновероятных исхода (пример 2.1.), которые можно обозначить ИСТИНА и ЛОЖЬ.

Единица измерения неопределенности при двух возможных равновероятных исходах опыта называется бит.

В опыте с n равновероятными исходами, каждый исход случаен и вносит свой вклад в неопределенность всего опыта. Неопределенность, вносимая одним исходом составляет

(2.1)

где р =1/n вероятность любого из отдельных исходов.

Если опыт  имеет п неравновероятных исходов А1, А2... Ап, то:

(2.2)

Введенная таким образом величина называется энтропией опыта . Формула (2.2) позволяет сравнить неопределенности различных опытов со случайными исходами.

Пример 2.3. Имеются два ящика А и В, в каждом из которых по 12 шаров. В первом - 3 белых, 3 черных и 6 красных; во втором - каждого цвета по 4. Опыты состоят в вытаскивании по одному шару из каждого ящика. Что можно сказать относительно неопределенностей исходов этих опытов?

Согласно (2.4) находим энтропии обоих опытов:

Ha=- 3/12 log2 3/12 -3/12log2 3/126/12 log2 6/12 = 1,50 бит, Нв=-4/12 log2 4/12- 4/12log2 4/12- 4/12log2 4/12 = 1,58 бит,

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

Рассмотрим два опыта  и , проводимые друг за другом. Предшествующий опыт  может уменьшить количество исходов и неопределенность последующего опыта . Разность Н() и Н() показывает, какие новые сведения относительно  получаем, произведя опыт . Эта величина называется информацией относительно опыта , содержащейся в опыте .

I(,) = Н(). (2.3)

Выражение (2.3) дает возможность численного измерения количества информации.

Поскольку единицей измерения энтропии является бит, то в этих же единицах может быть измерено количество информации. Пусть опыт =, т.е. просто произведен опыт . Поскольку он несет полную информацию о себе самом, неопределенность его исхода полностью снимается, т.е. Н() = 0. Тогда I(,) = Н(), т.е.

(2.4)

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

В данном случае n = 2 и события равновероятны, т.е. р1=p2 = 0,5. Из (2.4): I = -0,5*log2 0,5 - 0,5log2 0,5 = 1 бит.

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

Когда все п исходов равновероятны, все p(Ai)=1/n то:

(2.5)

Эта формула была выведена в 1928 г. американским инженером Р. Хартли и носит его имя. Ее смысл в том, что, если некоторое множество содержит n элементов, то для однозначной идентификации одного элемента среди прочих требуется количество информации, равное log2 n.
Пример 2.5. Случайным образом вынимается карта из колоды в 32 карты. Какое количество информации требуется, чтобы узнать, что это за карта? Как построить угадывание?

Для данной ситуации п = 32, следовательно, I = log232=5 бит.
Информация и алфавит

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

Нулевое приближение. Пусть появление всех знаков алфавита в сообщении равновероятно. Тогда для английского алфавита пе = 27 (с учетом пробела); для русского алфавита nг = 34. Из формулы Хартли (2.5) находим:

I0 (e) = log227 = 4,755 бит,

I0 (r) =log234 = 5,087 бит.

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

Первое приближение. Учтем, что вероятность появления различных букв в тексте различна (е=ё, ь=ъ, так принято в телеграфном кодировании). Получим алфавит из 32 знаков (с пробелом) со следующими вероятностями их появления в русских текстах:Таблица 2.1

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

Если сообщение является шенноновским, то набор знаков (алфавит) и связанная с каждым знаком информация известны заранее. В этом случае интерпретация сообщения, сводится к задаче распознавания знака.

Теория информации строится именно для шенноновских сообщений, поэтому в дальнейшем будем рассматривать только такие сообщения.

Применение формулы (2.4) дает значение средней информации на знак к алфавиту:

для русского языка I1(r)= 4,36 бит,

для английского языка I1)= 4,04 бит,

Второе приближение. Зачение средней информации на букву может быть уменьшено с учетом связей (корреляцией) между буквами в словах. В словах буквы появляются не в любых сочетаниях. Это понижает неопределенность угадывания следующей буквы, например, в русском языке нет слов, в которых встречается сочетание щц или фъ. И наоборот, после распространенного сочетания пр всегда следует гласная буква. Их в русском языке 10 и вероятность угадывания следующей буквы 1/10, а не 1/33. Учет в английских словах двухбуквенных сочетаний понижает среднюю информацию на знак до значения I2)= 3,32 бит, учет трехбуквенных - до I3)= 3,10 бит. Для русского языка дают; I2(r)= 3,52 бит; I3(r)= 3,01 бит.

Последовательность I0, I1, I2 -- является убывающей в любом языке. Шеннон ввел величину, которую назвал относительной избыточностью языка:

(2.14)

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

Исследования Шеннона показали, что для английского языка избыточность около 68%. Для русского избыточность 60-70%. Это означает, что возможно почти трехкратное сокращение текстов без ущерба для их содержательной стороны.

Кодирование символьной информации

Постановка задачи кодирования.

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

Код - (1) правило, описывающее соответствие знаков или их сочетаний первичного алфавита знакам или их сочетаниям вторичного алфавита. (2) набор - знаков вторичного алфавита, используемый для представления знаков или их сочетаний первичного алфавита.

Кодирование - перевод информации, представленной сообщением в первичном алфавите, в последовательность кодов. Декодирование - восстановление информации в первичном алфавите по полученной последовательности кодов.

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

Пусть первичный алфавит А состоит из N знаков со средней информацией на знак I(А), а вторичный алфавит В - из М знаков со средней информацией на знак I(B). Пусть исходное сообщение, представленное в первичном алфавите, содержит п знаков, а закодированное сообщение - т знаков. Операция обратимого кодирования может увеличить количество информации в сообщении, но не может его уменьшить. Отношение т/п характеризует среднее число знаков вторичного алфавита, которое приходится использовать для кодирования одного знака первичного алфавита. Оно называется длиной кода. Обозначим его К(А,В).

(3.1)

Обычно N>М и I(А)>I(В), откуда К(А,В)>1, т.е. один знак первичного алфавита представляется несколькими знаками вторичного. Способов построения кодов, при фиксированных алфавитах А и В существует множество, возникает проблема выбора оптимального кода, который при передаче информации позволяет затратить на передачу сообщения меньше времени.

Как следует из (3.1), минимально возможным значением средней длины кода будет:

(3.2)

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

Первая теорема Шеннона (основная

теорема о кодировании при отсутствии

помех): При отсутствии помех всегда

возможен такой вариант кодирования

сообщения, при котором среднее число

знаков кода, приходящихся на один знак

первичного алфавита, будет сколь угодно

близко к отношению средних информации

на знак первичного и вторичного алфавитов.

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

(3.3)

Превышение К(А,В) над Кmin(А,В) относительная избыточность кода Q(A,B):

(3.4)

Величина Q(A,B) показывает, насколько операция кодирования увеличила длину исходного сообщения. Q(A,B)0 при К(А,В) Кmin(А,В). Оптимизация кода состоит в нахождении таких схем кодирования, которые обеспечили бы приближение средней длины кода к значению Кmin(А,В).

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

Возможны следующие особенности вторичного алфавита, используемого при кодировании:

*элементарные сигналы (0 и 1) могут иметь одинаковые длительности (o=1) или разные (o1);

*длина кода может быть одинаковой для всех знаков первичного алфавита (равномерный код) или коды разных знаков первичного алфавита могут иметь различную длину (неравномерный код);

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

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

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

1.используется комбинация элементарных сигналов, которая интерпретируется декодером как разделитель знаков.

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

Неравномерный код с разделителем

Пусть разделителем отдельных кодов букв будет - 00 (признак конца знака), а разделителем слов-слов - 000 (пробел). Тогда код строится по правилам:

*кода всех букв будут заканчиваться 00;

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

*код буквы (кроме пробела) всегда должен начинаться с 1;

*разделителю слов 000 всегда предшествует признак конца знака; при этом реализуется последовательность 00000.

В соответствии с правилами построим кодовую табл. 3.1 для букв русского алфавита, основываясь на приведенных ранее (табл. 2.1.) вероятностях появления отдельных букв.

Таблица 3.1.

Код называется префиксным, если он удовлетворяет условию Фано:

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

Например, если имеется код 110, то уже не могут использоваться коды 1, 11, 1101, 110101 и пр. При использовании префиксного кодирования не нужно передавать разделители знаков, что делает сообщение более коротким.

Префиксный код Шеннона-Фано

Рассмотрим схему на следующем примере: пусть имеется первичный алфавит А, состоящий из шести знаков а1 ...а6 с вероятностями появления в сообщении 0,3; 0,2; 0,2; 0,15; 0,1; 0,05.

1.Расположим эти знаки в порядке убывания вероятностей.

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

3.Первой группе (а1 и а2 с суммой вероятностей 0,5) присвоим первый знак кода "0". Второй группе (сумма также 0,5)— первый знак кода "1".

4.Продолжим деление каждой из групп на подгруппы по этой же схеме.

В результате получаем :

Коды удовлетворяют условию Фано и, следовательно, код является префиксным.

Данный код не оптимальный, т.к. вероятности появления 0 и 1 неодинаковы (0,35 и 0,65). Применение схемы к русскому языку дает избыточность кода 0,0147.
Префиксный код Хаффмана

Рассмотрим построение кодов Хаффмана на том же примере.

1.Расположим знаки в порядке убывания вероятностей.

2.Создадим новый алфавит А(1), объединив два знака с наименьшими вероятностями (а5 и а6) и заменив их одним знаком а(1) с вероятность равной сумме вероятностей а5 и а6.

3.Остальные знаки включим в новый алфавит без изменения. Общее число знаков в новом алфавите будет на 1 меньше, чем в исходном.

4.Переупорядочим знаки по убыванию вероятностей.

5.Продолжим создавать новые алфавиты, пока в последнем не останется два знака.

Всю процедуру построения предстоим в виде таблицы:



Проведем кодирование в обратном направлении. Двум знакам последнего алфавита присвоим коды 0 и 1 (верхний знак — 0, а нижний — 1). В примере знак а1(4) алфавита А(4) имеющий вероятность 0,6 получит код 0, а а2(4) c вероятностью 0,4 - код 1. В алфавите А(3) знак а1(3) получает от а2(4) его вероятность 0,4 и код 1; коды знаков а2(3) и а3(3), происходящие от знака а1(4) с вероятностью 0,6 будут уже двузначным: их первой цифрой станет код их «родителя» (0), а вторая цифра - как условились - у верхнего 0, у нижнего - 1; таким образом, а2(3) будет иметь код 00, а а3(3) - код 01 и т.д. Процедура кодирования представлена в таблице .



Коды удовлетворяют условию Фано и, следовательно, не требуют разделителя. Средняя длина кода: К(А,2) = 0,3*2 + 0,2*2 + 0,2*2 +0,15*3 + 0,1*4 + 0,05*4 = 2,45.

Избыточность Q(А,2) = 0,0249, однако, вероятности 0 и 1 сблизились (0,47 и 0,53).

Более высокая эффективность кодов Хаффмана по сравнению с кодами Шеннона-Фано становится очевидной, если сравнить избыточности кодов для естественного языка. Применение описанного метода для букв русского алфавита порождает коды, представленные в табл. 3.2.

Код Хаффмана является самым экономичным из всех возможных, т.е. ни для какого метода алфавитного кодирования длина кода не может оказаться меньше, чем код Хаффмана.
Представление и обработка чисел в компьютере

Системы счисления

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

Любое число имеет значение и форму представления. Значение числа задает его отношение к значениям других чисел (>, <, =). Форма представления определяет порядок записи числа с помощью предназначенных для этого знаков. Значение числа не зависит от способа его представления. Способ представления числа определяется системой счисления. Система счисления - это правило записи чисел с помощью заданного набора специальных знаков - цифр.

Способы записи чисел делятся на 3 группы:

1. Унарная - это система счисления, в которой для записи чисел используется только один знак - I («палочка»). Следующее число получается из предыдущего добавлением новой I. Их количество равно самому числу.

2. В непозиционной базовые числа обозначены латинскими буквами: 1-I, 5-V, 10-Х, 50-L, 100-С, 500-D, 1000-М (римская система счисления). Все другие числа строятся комбинаций базовых. Например, XIX — 19, MDXLIX — 1549.

3. Позиционными называются системы счисления, в которых значение каждой цифры в изображении числа определяется ее позицией в ряду других цифр. Наиболее распространенной является система счисления, в которой для записи чисел используется 10 цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9. Число представляет собой краткую запись многочлена, в который входят степени некоторого другого числа - основания системы счисления. Например,

272 = 2*102+ 7*101 + 2*10°.

По принципу, десятичной системы счисления, можно построить системы с другим основанием. Пусть р - основание системы счисления. Тогда число Zр может быть представлено в виде:

(4.1)

где р - основание системы счисления, k - общее число цифр (целое, k>0), aj - целые числа.

Определим минимальное значение р. р = 1 невозможно, поскольку тогда все аj = 0 и форма (4.1) теряет смысл. Первое допустимое значение р = 2 является минимальным для позиционных систем. Система счисления с основанием 2 называется двоичной. Цифрами являются 0 и 1, а форма (4.1) строится по степеням 2

Представление чисел в различных системах счисления

Перевод числа из системы р в q обозначим ZpZq. Его возможно произвести при любых q и р, но он затруднен тем, что придется выполнять операции по правилам арифметики недесятичных систем счисления. Поэтому удобными являются преобразования ZpZ10Zq .

Преобразование ZpZ10Zq

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

Алгоритм перевода Z10Zq:

1.целочисленно разделить исходное число Z10 на основание новой системы счисления q и найти остаток от деления - это будет цифра 0-го разряда числа Zq.

2.частное от деления снова целочисленно разделить на q с выделением остатка; процедуру продолжать до тех пор, пока частное от деления не окажется меньше q;

3.образовавшиеся остатки от деления, поставленные в порядке, обратном порядку их получения, и представляют Zq.
Пример 4.1. Выполнить преобразование 12310 Z5,

Остатки от деления (3, 4) и результат последнего целочисленного деления (4) образуют обратный порядок цифр нового числа. Следовательно, 12310=4435.
Алгоритм перевода Zp Z10:

1.необходимо Zp представить в форме многочлена (4.1)

2.выполнить все операции по правилам десятичной арифметики.

Пример 4.2. Выполнить преобразование 4435  Z10

4435 = 4*52+ 4*51 + 3*5° = 4*25 + 4*5 + 3*1 = 12310

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

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

Для записи числа в устройствах компьютера выделяется фиксированное количество двоичных разрядов. Память компьютера имеет байтовую структуру, размер одной адресуемой ячейки обычно составляет несколько байт. Например, в компьютерах IBM ячейка памяти объединяет 2 байта (16 двоичных разрядов). Комбинация связанных соседних ячеек, обрабатываемая совместно, называется машинным словом. Для представления числа в регистре арифметико-логического устройства процессора, где формируется результат операции, имеется еще один дополнительный одноразрядный регистр, который называется регистром переноса и который можно рассматривать в качестве продолжения (т.е. 17-го бита) регистра результата.

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



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

Умножение производится согласно таблице умножения, которая для двоичных чисел имеет вид:


Пример 4.9. Найти произведение 1310*510 .Операции выполнить в двоичной системе счисления.



Передача информации

Общая схема передачи информации в линии связи

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


Рис. 5.1. Общая схема передачи информации

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

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

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

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

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

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

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

хранения информации

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

Любой канал связи обладает рядом характеристик:

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

2.Длительность элементарного импульса.

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

4.Скорость передачи информации - количество информации I, которое может быть передано по каналу связи за время t.

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

Вторая теорема Шеннона: При передаче

информации по каналу с шумом всегда

имеется способ кодирования, при котором

сообщение будет передаваться со сколь

угодно высокой достоверностью, если

скорость передачи не превышает пропускной

способности канала.

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

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

установление факта искажения информации - в этом случае исправление производится путем ее повторной передачи;

*кодирование позволяет определить и автоматически исправить ошибку передачи.

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

Коды, обнаруживающие ошибку

Задача обнаружения ошибки может быть решена довольно легко. Достаточно передавать каждую букву сообщения дважды. Например, слова «гора» можно передать «ггоорраа». При получении сообщения «гготрраа» можно догадаться, каким было исходное слово. Возможно искажение, которое делает неоднозначным интерпретацию полученного сообщения, например, «гпоорраа». Цель такого способа кодирования состоит не в исправлении ошибки, а в фиксации факта искажения и повторной передаче части сообщения. Недостаток данного способа обеспечения надежности состоит в том, что избыточность сообщения оказывается очень большой, L = 2.

Для обнаружения ошибки можно использовать другой способ кодирования. Пусть имеется цепочка информационных бит длиной ki. Добавим к ним один контрольный бит (kс=1), значение которого определяется тем, что новая кодовая цепочка из ki+1 бит должна содержать четное количество единиц - по этой причине такой контрольный бит называется битом четности. Например, для информационного байта 01010100 бит четности будет иметь значение 1, а для байта 11011011 бит четности равен 0. В случае одиночной ошибки передачи число 1 перестает быть четным, что и служит свидетельством сбоя. Например, если получена цепочка 110110111 (контрольный бит выделен подчеркиванием), ясно, что передача произведена с ошибкой, поскольку общее количество единиц равно 7. Этот способ кодирования не позволяет установить, в каком конкретно бите содержится ошибка и не дает возможности ее исправить. Избыточность сообщения при этом равна (5.6):



На первый взгляд кажется, что путем увеличения ki, можно сколь угодно приближать избыточность к ее минимальному значению (Lmin = 1). С ростом ki растет вероятность парной ошибки, которая контрольным битом не отслеживается, при обнаружении ошибки потребуется заново передавать много информации. Поэтому обычно ki=8 или 16 и L = 1,125 (1,0625).
Коды, исправляющие одиночную ошибку

По аналогии с предыдущим пунктом можно было бы предложить простой способ установления ошибки - передавать каждый символ трижды, например, «гггооорррааа» - тогда при получении сообщения «гггооопррааа» ясно, что ошибочной оказывается буква «п» и ее следует заменить на «р». Безусловно, при этом предполагается, что вероятность появления парной ошибки невелика. Такой метод кодирования приводит к избыточности сообщения L = 3, что неприемлемо с экономической точки зрения.

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

H=-p*log2p-(1-p)*log2(1-p)

Для восстановления информационного содержания сообщения следует дополнительно передать количество информации не менее величины ее потерь, т.е. вместо передачи каждого 1 бит информации следует передавать 1+Н, бит. В этом случае избыточность сообщения составит

(5.7)

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

Пример 5.3

Какое минимальное количество контрольных бит должно передаваться вместе с 16-ю информационными для обеспечения восстановимости информации, если вероятность искажения составляет 1%?

Подставляя р = 0,01 в (5.7), находим Lmin = 1,081.

При ki= 16 из (5.6.) получаем к = ki * Lmin = 17,29.

С учетом того, что количество контрольных бит выражается целым числом, kсk- ki = 2.

Реальная избыточность согласно (5.6) составит L= 1,125.

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

Идея состоит в добавлении к информационным битам нескольких битов четности, каждый из которых контролирует определенные информационные биты. Если пронумеровать все передаваемые биты, начиная с 1 слева направо (информационные биты нумеруются с 0 и справа налево), то контрольными оказываются биты, номера которых равны степеням числа 2, а все остальные являются информационными. Например, для 8-битного информационного кода контрольными окажутся биты с номерами 1, 2, 4 и 8 (слайд):



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

Таблица 5.1.(слайд)

Для любого номера проверочного бита n, начиная с него, n бит подряд оказываются проверяемыми, затем - группа n непроверяемых бит; далее происходит чередование групп.

Пример 5.4

Пусть вместо последовательности 000111011101 пришла следующая последовательность (в 5-м бите 1 заменилась 0):

Анализируем состояния контрольных битов в соответствии с табл. 5.1.

Бит 1 - неверно - т.е. ошибка находится в каком-либо бите с нечетным номером.

Бит 2 - верно - следовательно, из байтов с нечетными номерами 3, 7 и 11 верны (т.е. ошибка в 5 или 9-м).

Бит 4 - неверно - значит, ошибка может содержаться только в 5-м бите.

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

Номер бита, содержащего ошибку (5), равен сумме номеров контрольных битов, указавших на ее существование (1 и 4) -это общее свойство кодов Хемминга.

Алгоритм проверки и исправления передаваемой последовательности бит в представлении Хемминга:

1.произвести проверку всех битов четности;

2.если все биты четности верны, то перейти к п.5;

3.вычислить сумму номеров всех неправильных битов четности;

4.инвертировать содержимое бита, номер которого равен сумме, найденной в п.3;

5.исключить биты четности, передать правильный информационный код.

Избыточность кодов Хемминга для различных длин передаваемых последовательностей приведена ниже (слайд):

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






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