Савельвев А.Я. Основы информатики

Подождите немного. Документ загружается.

/ 5 Преобразование информации

счетов функции на отрезке обработки будет большим и точность воспроиз-

ведения — высокой. При больших шагах дискретизации количество отсче-

тов уменьшается, но при этом, как правило, снижается точность восстанов-

ления. Оптимальной является такая дискретизация, которая обеспечивает

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

количестве отсчетов.

Меюды дискретизации и восстановления информации классифициру-

ются в (ависнмости от регулярности отсчета, критерия оценки точности

дискретизации и восстановления, вида базисной функции, принципа при-

ближения.

Pei у;гяриость отсчета определяется равномерностью дискретизации.

Дискретизация называется равномерной (рис. i.4, о), если длительность

ишервалов Л/, ^ const на всем отрезке обработки сигнала. Методы равно-

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

для их peajm^anHH достаточ1ю просты. Однако при этом возможна значи-

1ельная избыточность отсчетов.

i, Ч h и ^ h i

Рис.

1.4. Способы дискретизации информации

Днскретизация называется неравномерной (рис.

\Л,б),

если длитель

носп. ии!ервалов между отсчетами А/, различна, т. е. А/, -var. Вы^еляку

две труппы неравномерных методов: адаптивные и программируемые. Flpi

адашивных мсюдах итервалы А/, изменяются в зависимости от текущей

ишспения 1гарамегров сигналов. При программируемых методах интерва

jM.i Л/, п!ме!1Я101ся либо оператором па основе анализа поступающей ин

формации, либо в соответствии с заранее установленной пр01раммой работы

Криюрин оценки точности дискретизации сигнала выбираются полу

ча1слсм ип!|юрмаиии и зависят от целевого истюльзования сигнала и воз

можпостей аппаратной (npot раммной) реализации. Чаще других использу

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

nnicfpaJH.nMH и вероятностный.

Базовые

понятия

информатики

Тип базисных (приближающих, воспроизводящих) функций в основ-

ном определяется требованиями ограничения сложности устройств (про-

грамм) дискретизации и восстановления сигналов.

Воспроизводящие функции v(/) обычно совпадают с приближающими

функциями pit), хотя в общем случае они могут отличаться друг от друга.

Чаще всего для дискретизации и восстановления используют ряды Фурье и

Котельиикова, полиномы Чебышева и Лежаидра, степенные полипомы,

функции Уолша и Хаара, гипергеометрические функции.

При равномерной дискретизации шаг

и частота отсчетов F,, — по-

стоянные величины (рис. 1.4, а). Модель равномерной дискретизации очень

хороню подходит к модели синхронных автоматов. 'Георема Ко1ельпнкова

позволяет осуществлять выбор шага дискретизации, что существен!ним об-

разом может повлиять на количество и скорость [юсгупления информации

для обработки.

Квантование по уровню состоит в преобразовании непрерывных зна-

чении сигнала х(1,) в моменты отсчета /,, в дискретные значения (рис. 1.5).

В соответствии с графиком изменения функции х(1) ее ис1инные значения

представляются в виде заранее заданных дискретных уровней /, 2. 3, 4. 5

HJHi 6. <1>ункция в момепть[ отсчета может задаваться

HJHI ГОЧПО

(шачс-

ние Xj — уровень 4). или с некогорой по-

грешностью (значение х, — уровень 2. зна-

чение х, — уровень б).

Квантование по уровню может бы и, рав-

номерным и неравномерным в зависимости

величины шага квантования. Под шагом {ш\-

~^ тервалом) квантования 5^ гюинмаегся раз-

ность 5 =х„,~х ,, где

I э^

*м tt

Рис.

1.5. Квантование

по

\pUBMIO

x„,_t

— сосе;1Ние

уровни квантования.

Уровень квантования для заданного значе-

ния сигнала х{1) можно выразить двумя способами:

1) сигнал х(/,) отождествляется с ближайшим уровнем квагпования;

2) сигнал х(/,) отождествляегся с ближайшим меньшим (или боль-

шим) уровнем квантования.

Так как в процессе преобразования значение сигнала x{t) отображает-

ся уровнем квантования х„,, а каждому уровню т может быть посгавлеи в

соответствие свой номер (число), то при передаче или хранении ииформа-

/.5.

Преобразование информации

ции МОЖНО вместо истинного значения величины х„, использовать соответ-

ствующее число т. Истинное значение уровня квантования легко восстано-

ви и., зная масштаб по шкале х. Для представления т уровней квантования

с помощью неизбыточного равномерного кода потребуется и = 1о§,т раз-

рядов. Такое преобразование сопровождается шумами или погрешностью

квантования. Погрешность квантования связана с заменой истинного зна-

чения сигнала х{1,) значением, соответствующим уровню квантования :с„,.

Максимальная погрешность квантования зависит от способа отождествле-

ния си[ нала с уровнем квантования. Для первого из рассмотренных спосо-

бов она равна 0,55„,, для второго — 5„,.

Чем меньше шаг квантования, тем меньше погрешность квантования.

Можно принять, что погрешность квантования в пределах шага квантова-

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

функции в пределах шага будет равновероятным.

[1аиболее часто используются степенные алгебраические полиномы

вн;ц1

У{1)

- ^а/ .

де // — степень полинома, а, — действительные коэф-

фипиепЕЫ. Ич T[()fo класса функций наиболее полно исследовано примене-

пне полиномов нулевой и первой степени. Алгебраические полиномы

удобны для программирования и обработки на ЭВМ.

Выбор огггимальной системы функции представляет определенные

рудное

и, гак как при решении задачи минимизации числа дискретных

харак1еристик д;[я описания сигнала с заданной точностью должны учиты-

вать слоЖ1гость ап1!аратуры (программ), допустимое время задержки в вы-

;шче информаг^ии и другие факторы.

Метод дискрегизации при преобразовании непрерывной информации в

дискретную влияет на количество информации, которую надо хранить или

преобразовывать в ЭВМ. Важна теорема Котельникова, согласно которой

функция, имеющая ограниченный спектр частот, полностью определяется

дискрет ным множеством своих значений, взятых с частотой отсчетов;

/=о=2Л,, (1.9)

дс /„, - 27гоэ,„ — максимальная частота в спектре частот S(j(i}) сигнала

^(0^

f^L*,,, угловая скорость.

Функция л(/) воспроизводится без погрешностей по точным значе-

ниям x(ij в виде ряда Котельникова:

Базовые

понятия

информатики

где А/ — шаг дискретизации.

Георема Котельникова справедлива для сигналов с о!раниченным

спектром. Реальные сигналы — носители информации — имеют конечную

длительность. Спектр таких сигналов не ограничен, т. е. реальные сигналы

не соответствуют в точности модели сигнала с о1раниче11ным cricKipuM, и

применение теоремы Котельникова к реальным сигналам связано с по-

грешностями при восстановлении сигналов по формуле (1.10) и неопреде-

ленностью выбора шага дискретизации или частоты отсчетов.

Для практических задач, однако, идеально точное восстановление

функций не требуется, необходимо лишь восстановление с заданной тоЧ1ю-

стью.

Поэтому теорему Котельникова можно рассматривать как

HPHGJHI-

женную для функций с неограниченным спектром. На практике часгогу

отсчетов часто определяют по формуле

^а-2/„,Д,, (КМ)

где к^ — коэффициент запаса (обычно 1,5 < А, 5 6); /^^^^ — waKCHMajn.-

ная допустимая частота в спектре сигнала х{1), например, с учетом доли

nojmoH эггергии, сосредоточенной в ограниченном частотой ciicKipe сиг-

нала.

Из вышеизложенного следует, что преобразование непрерывной ин-

формации в дискретную можег сопровождаться сжатием ин[])ормацпн

(уменьшением ее количества). Кварповаиие по ypOBiiio — один из способов

сжатия информации.

Квантование и дискретизация находят iiHipoKoe применение в преобра-

зователях информации, используемых при связи ЭВМ с конкреигыми объ-

ектами (процессами).

1.6. Формы представления информации

Информация всегда представляется в виде сообщения, которое переда-

егся некоторой физической средой. Носителем информации может быть

любая предметная среда, которая меняет состояние в зависимости от Fiepe-

даваемой информации. Это может быть бумага, на которой информация

изображается либо знаками, либо специальными отметками (например,

перфорация); магнитный материал (лента, диск и т. п.), состояние которою

/ б Формы представления информации

Меняется с помощью магнита; электрический сигнал, у которого изменяется

какой-либо liapaMCTp (частота, амплитуда).

Различают две формы представления информации: статическую 7^.,

(рис.

1.6, а) и динамическую /^, (рис. 1.6, б). Возможность передачи сооб-

щения посредством электрического сигнала реализуется с помощью канала

связи, соединяющего источник и приемник информации (рис. 1.7). Чтобы

передать ин([)Ормацию, необходимо ее

предварительно преобразовать.

Кодирование — преобразование со-

общения в форму, удобную для передачи

Г10 /рапному каналу. В качестве простого

примера можно привести передачу со-

общения в виде телеграммы. Все симво-

лы кодируются с гюмощью телеграфного

кода.

Декодирование — операция восста-

новления принятого сообщения. В сис-

тему связи необходимо ввести устрой-

ства для кодирования и декодирования

иргформации (рис. 1.8). Теоретическое

обоснование таких систем дал в своих

работах К, Шенпон. Рядом теорем он

показал эффективность введения коди-

pyioniHx и декодирующих устройств,

nnnta'iemic коц>рых состоит в согласо-

вании СВ0ЙС1В источника информации со свойствами канала связи. Одно

из них (кодирующее устройство, или кодер) должно обеспечить такое ко-

дироват1е, при котором путем устранения избыточности информации

eyiiieciBenno снижается среднее число символов, приходящееся на едини-

цу сообщения. При отсутствии помех это непосредственно дает выигрыш

во времени [|ередачи или в объеме запоминающего устройства. Такое ко-

дирование называют эффективным (или оптимальным)^ так как оно по-

RbHiiaei эффективность системы. При наличии помех в канале передачи

он^) позволяет преобразовать входную информацию в последовательность

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

разоват^я. Другое кодирующее устройство (кодер канала) обеспечивает

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

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

naibiBaiOT избыточным или помехоустойчивым. Помехоустойчивость

Рнс. 1.6

информа-

ции

1 ' 1 *

Формы представления

информации

Кана/t

Приемным

ин форма-

ц,ии

Рис.

1.7. Информационная модель

канала связи

/, Базовые понятия иифор)

шатики

достигается учетом не только интенсивности помехи, но и ее статистиче-

ских закорюмерностей.

Кодирующее

|_J

^одер

\^аиая

^Ш,екаВер\

устрпйстВо\ канала связи \\мйиапа\ L

leKoSapytcuiee

цс^ройегпвв

Приемник

Рис.

1.8. Информационная модель канала связи с шумами

Целесообразность устранения избыточности сообщения методами эф-

фективного кодирования с последующим перекодированием помехоустойчи-

вым кодом обусловлена тем, что избыточность источника сообщения в

большинстве случаев не согласована со статистическими закономерностями

помехи в канале связи и поэтому не может быть полностью использована ;для

повышения достоверности принимаемого сообщения. Кроме того, избьпоч-

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

Если избыточность источника сообщений мала и помехи в канале

связи практически отсутствуют, то введение как кодера источника, так и

Кодера канала нецелесообразно. Если избыточность источника сообщений

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

Если избыточность источника мала, а помехи велики, то целесообразно

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

целесообразно ввести оба дополнительных кодирующих (и декодирую-

щих) устройства. Большинство кодов, используемых при кодировании

информации без учета статистических свойств источника и 1юмехи в ка-

нале связи, основано на системах счисления.

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

Современные вычислительные средства (персональные ЭВМ, микро-,

мини- и максиЭВМ) часто используются в составе вычислительных систем

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

THBHoio представления информации, но также вопросы передачи информа-

ции по каналам связи без искажений. В качестве каналов связи (рис, 1,9)

могут использоваться: непосредственная связь ИС пользователя вь!числи-

тельными средствами, телефонный канал ТлК^ телеграфный канал />/<", рн~

диоканш! РК^ телевизионный канал ТвК, другие виды связи.

Вид канала определяет характер и величину помех, которые при этом

появляются. Поэтому инженер-проектировщик ЭВМ должен учитывать эти

обстоятельства при разработке технических, математических и программ-

ных средств.

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

Рассмотрим некоторые общие во-

Пользователи

просы,

возникающие при передаче ин-

формации.

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

лу без помех. Если через канал связи

без помех передается последователь-

ность дискретных сообщений

дли-

тельностью Т. то скорость передачи

информации \\о каналу связи (бит/с)

V- Пт(//Г), (1.12)

где / " количество информации, со-

держащейся в последовательности со-

о6и№иий.

Предельное значение скорости

передачи информации называется

пропускной сгюсобиостью канала

свя-

зи без помех с -• v,„a^.

Количество информации в сооб-

щениях максимально при равной вероятности состояний. Тогда

lim logj к/Т .

/Пользователи

Рис. 1.9. Каналы связи в

вычислительных сетях

(1.13)

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

ских свойств сооб1цепий и параметров канала связи.

Пропускная способность — характеристика канала связи, которая не

записи!

01 скорости передачи информации. Количественно пропускная

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

ных единиц информа[|ИИ, которое данный канал связи может передать за

одну секунду.

/1ля !1аиболее эффективного использования канала связи необходимо,

чюбы CKOpocib передачи информации была как можно ближе к пропускной

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

Kanajta связи превышает пропускную способность канала, то по каналу бу-

дет передана не вся ин([}ормацня. Основное условие согласования источни-

ка информации и канала связи

v<c. (1.Г4:

Согласование осуществляется путем соответствующего кодирования со-

общений.

Доказано, что если скорость информации, вырабатываемой источ-

/, Базовые понятия иифор.

шатики

НИКОМ сообщений v^ , достаточно близка к пропускной способности канала

с, т. е. v^ - с - 8, где 8 — сколь угодно малая величина, то всегда можно

иайти такой способ кодирования, который обеспечит передачу cooGiue-

иий, вырабатываемых источником, причем скорость передачи информа-

ции будет весьма близка к пропускной способности канала.

Верно и обратное >тверждение: невозможно обеспечить длительную пе-

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

ком, превышает пропускную способность канала.

Если ко входу канала подключен источник сообщений с э1ггропией,

равной пропускной способности канала связи, то считается, что исючиик

согласован с каналом. Если энтропия источника меньше пропускной С1ю-

собности канала, что может быть в случае неравновероятгюстн состояний

источника, то источник не согласован с каналом, т. е. канал используется не

полностью.

Согласование в статистическом смысле достигается с помощью сгаги-

стического кодирования. Оно позволяет повысить энтропию передаваемых

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

вательности равновероятны. При этом число cимвoJюв в последова!елы!о-

сти будет сокращено. В результате источник информации согласуется с ка-

налом связи.

Передача информации по каналу с номехамм. При передаме инфор-

мации через канал с помехами сообщения искажаются, и на приемной сто-

роне иет уверенности в том, что принято именно то сообщение, которое

передавагюсь. Следовательно, сообщение недостоверно, вероятность пра-

вильности его после приема не равна единице. В этом случае KojnmeciBo

получаемой информации уменьшается на величину неопределенности, вно-

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

после приема: /'==//(/)-Я,(/), где H{i) — энтропия источника сообще-

ний; Я,(/) — энтропия сообщений на приемной стороне.

Таким образом, скорость передачи по каналу связи с 1юмехами

,.,,„„ Я(0-Я.(/) ,

•1^^

пропускной способностью капала с шумами называется максимальная

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

гласован с источником информации:

с- lim-2^^.

Задания для самоконтроля

Вели энтропия источника информации не превышает пропускной спо-

собности канала (И<с),

то

существует код, обеспечивающий передачу

информации через канал

1юмехами со сколь угодно малой частотой оши-

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

канала связи при ограниченной средней мощности аналогового сигнала

c^F„,\og2{\

lVJlV^J,

(1.16)

где

F,„ —

полоса частот канала (Гц); fV^

—

средняя мощность сигнала;

И'и,

—

средняя мощность помех (равномерный спектр)

нормальным за-

коном распрс/челения амплитуд в полосе частот канала связи.

Следова^ельгго, можно передавать информацию по каналу

помехами

без огиибок, если скорость передачи информации меньше пропускной спо-

собности канала, определяемой формулой (IJ6). Для скорости

v>c при

любой системе кодирования частота ошибок принимает конечное значение,

причем оно pacTCi с увеличением значения

Из выражения (1.16) следует,

что для Kariajia

весьма высоким уровнем шумов {W^

W^) максимальная

скорость передачи близка

нулю.

Залания лля самоконтроля

Яиляижя JMI слонами следующие комбипамии'

at корабль. 0)ашш, и) !2345;г) !а25ЛВС

Чю гакос «6vi!»'.'

3. Какое ко.'тичссгво информации можно изобразить

помощью двадиатиразрядных де-

смиг'ип.гч чисел''

каких cjr> чаях сгатистическая мера информации совггадает с аддитивной мерой?

5. Опролелиге ироиускиут способность канала связи,

котором отношение полезного

СИ1

нала

еи1

нал\ помехи составляет:

а)

1.2.6)0,2

Полоса 4i!ci<>[ ктиига

Mi'u

АВТОМАТ КАК ОСНОВНОЙ ЭЛЕМЕНТ

ИНФОРМАЦИОННЫХ СИСТЕМ

2.1.

ЭВМ как автомат

Здесь полезно вспомнить слова В. М. Глушкова о том, чго «электрон-

ные цифровые машины с программным управлением представляют собой

пример о;июго из наиболее распространенных в настоящее время гинов

преобразователей дискретной информации, называемых дискретными и;[И

цифровыми автоматами» [6]. С точки зрения пользователя вычислительная

машина представляется в виде некоего «черного ящика», выполняющего

достаточно сложные и многочисленные операции при решении самых раз-

нообразных задач. О том, как устроен этот «черный ящик», можно гюлу-

чить достаточно подробные сведения, проведя тщательный аР1ализ про-

цессов представления, г!реобразования и Переработки информации,

1еобходимо выделить несколько важных положений.

[|режде

всего, любая вычислительная машина (ВМ) работае!

автоматически (будь то большая или малая ЭВМ, персональный комггь-

ютер или Супер-ЭВМ). В этом смысле ВМ как автомат может быть описана

структурной схемой, представлернюй на

рис.

2.[. Элементы этой структурной схемы

применительно к электронным вычислитель-

ным машинам (ЭВМ) универсального назначе-

ния могут быть определены следующим обра-

зом (рис. 2.2).

В качестве ис11олнительных элементов в

автомат включаются;

— арифметико-логическое усфойство

(AJfV};

— память;

— устройства ввода—вывода информа-

ции.

Управляющим элементом автомата является устройство управления

(УУ),

которое собственно обеспечивает автоматический режим работы.

Упрй8лвющие

устроиста

ASmonam

Испйднитеяь-

устройств

8cnoMotame№

ные ^

устройства

Рис.

2.1.

Обобщенная

блок-схема алтомата