Подключение библиотек подпрограмм 4 страница

Например, в алфавите А = {а, b, с} имеются слова N=ab, М=bcb, К=аbсbсbаb. Заменив в слове К слово N на М, получим bcbcbcbab или abcbcbbcb, и, наоборот, заменив М на N, получим aabcbab или abcabab.

Подстановка ab-bcb недопустима к слову bacb, так как ни ab, ни bcb не входит в это слово. К полученным с помощью допустимых подстановок словам можно снова применить допустимые подстановки и т.д. Совокупность всех слов в данном алфавите вместе с системой допустимых подстановок называют ассоциа­тивным исчислением. Чтобы задать ассоциативное исчисление, достаточно задать алфавит и систему подстановок.

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

Последовательность слов Р, P1, Р2,..., М называется дедуктивной цепочкой, веду­щей от слова Р к слову М, если каждое из двух рядом стоящих слов этой цепочки – смежное.

Слова Р и М называют эквивалентными, если существует цепочка от Р к М и обратно.

Пример:

Алфавит Подстановки

{а, b,с,d, е} ас – са; abac – abace;

ad – da; eca – ae;

bc – cb; eda – be;

bd – db; edb – be.

Слова abcde и acbde – смежные (подстановка bc – cb). Слова abcde – cadbe эквива­лентны.

abcde ® acbde ® cabde ® cadbe

(bc-cb) (ac-ca) (bd-db)

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

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

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

Пример:

Алфавит: Система подстановок В:

А = {а, b, с} cb-cc

сса – ab

ab – bса

Предписание о применении подстановок: в произвольном слове Р надо сделать возможные подстановки, заменив левую часть подстановок на правую; повторить процесс с вновь полученным словом.

Так, применяя систему подстановок В из рассмотренного примера к словам babaac и bcacabc, получаем:

b ab aac ® bbcaaac ® остановка, т.к. в полученном слове больше нет допустимых подстановок;

bcac ab c ® bca cb cac ® bcac cca c ® bcacabc ® бесконечный процесс (остановки нет), так как мы получили исходное слово.

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

Такой набор предписаний вместе с алфавитом А и набором подстановок В опре­деляют нормальный алгоритм. Процесс останавливается только в двух случаях: 1) когда подходящая подстановка не найдена; 2) когда применена последняя под­становка из их набора. Различные нормальные алгоритмы отличаются друг от друга алфавитами и системами подстановок.

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

Пример:

Алфавит: Система подстановок В:

А= {+, 1} 1 + ® + 1

+ 1 ® 1

1 ® 1

Слово Р: 11+11+111.

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

 

Р = 1 1+ 11+111 Р5 = + 1+ 111111

Р1 = 1+ 111+111 Р6 = + +1 111111

Р2 = +111 1+ 111 Р7 = +1 111111

Р3 = +11 1+ 1111 Р8 = 1111111

Р4 = +1 1+ 11111 Р9 = 1111111

 

С Р по Р5переработка осуществляется с помощью первой подстановки. В Р6, Р7используется вторая подстановка, т.к. первые подстановки исчерпаны. В Р8, Р9применяется последняя подстановка и процесс останавливается.

Нормальный алгоритм Маркова можно рассматривать как универсальную форму задания любого алгоритма. Универсальность нормальных алгоритмов декларируется принципом нормализации: для любого алгоритма в произвольном конечном алфави­те A можно построить эквивалентный ему нормальный алгоритм над алфавитом А.

Разъясним последнее утверждение. В некоторых случаях не удается построить нормальный алгоритм, эквивалентный данному в алфавите А, если использовать в подстановках алгоритма только буквы этого алфавита. Однако, можно построить требуемый нормальный алгоритм, производя расширение алфавита А (добавляя к нему некоторое число новых букв). В этом случае говорят, что построенный алго­ритм является алгоритмом над алфавитом А, хотя он будет применяться лишь к словам в исходном алфавите А.

Если алгоритм N задан в некотором расширении алфавита А, то говорят, что N есть нормальный алгоритм над алфавитом A.

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

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

· Суперпозиция алгоритмов. При суперпозиции двух алгоритмов А и В выходное слово первого алгоритма рассматривается как входное слово второго алгоритма В; результат суперпозиции С может быть представлен в виде С(р) = В(А(р)).

· Объединение алгоритмов. Объединением алгоритмов А и В в одном и том же алфавите называется алгоритм С в том же алфавите, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В, в записан­ные рядом слова А(р) и В(р).

· Разветвление алгоритмов. Разветвление алгоритмов представляет собой ком­позицию D трех алгоритмов А, В и С, причем область определения алгоритма D является пересечением областей определения всех трех алгоритмов А, В и С, а для любого слова, р из этого пересечения D(p) = А(р), если С(р) = е, D(p) = B(p), если С(р) = е, где е – пустая строка.

· Итерация алгоритмов. Итерация (повторение) представляет собой такую композицию С двух алгоритмов А и В, что для любого входного слова р соответст­вующее слово С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.

Нормальные алгоритмы Маркова являются не только средством теоретических построений, но и основой специализированного языка программирования, приме­няемого как язык символьных преобразований при разработке систем искусствен­ного интеллекта. Это один из немногих языков, разработанных в России и полу­чивших известность во всем мире.

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

 

3.2. Обработка аналоговой и цифровой информации. Кодирование информации

 

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

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

· ввод информации или установка исходных данных;

· переработка или преобразование введенной информации;

· определение результатов и вывод переработанной информации.

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

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

Дискретный сигнал – сигнал, принимающий бесконечное число значений и заданный в дискретном времени (определен только в моменты времени, кратные периоду дискретизации Т).

Цифровой сигнал – сигнал, принимающий конечное число значений, заданный в дискретном времени и представленный в виде цифровых кодов.

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

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

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

Процесс дискретизации состоит обычно из двух этапов: дискретизации по времени и дискретизации (кванто­вания) по уровню.

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

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

Период дискретизации Дt – интервал времени между двумя последовательными отсчетами аналогового сигнала (шаг дискретизации по времени).

При выборе частоты дискретизации по времени можно воспользоваться теоремой В.А. Котельникова.

Теорема отсчетов (теорема Котельникова) – теорема, определяющая выбор периода дискретизации Дt аналогового сигнала в соответствии с его спектральной характеристикой.

Согласно теореме, всякий непрерывный сигнал, имеющий ограниченный частотный спектр, полностью определяется своими дискрет­ными значениями в моменты отсчета, отстоящие друг от друга на интервалы времени Дt = l/(2Fmax), где Fmax – макси­мальная частота в спектре сигнала. Иначе, дискретизация по времени не связана с потерей информации, если частота дискретизации fдискр= 1/Дt в два раза выше указанной верх­ней частоты сигнала Fmax.

Согласно теореме Котельникова, нет необходимости пе­редавать бесконечное множество всех значений непрерывного сигнала x(t), достаточно передавать лишь те его значения (рис. 3.4), которые отстоят друг от друга на расстоянии Дt = l/(2Fmax). Для восстановления сигнала x(t) на вход идеального фильтра низких частот, имеющего полосу про­пускания частот от 0 до Fmax, необходимо подать последо­вательность узких импульсов с амплитудой, соответствую­щей дискретным отсчетам сигнала x(ti) в моменты времени ti=iДt.

 

Рис. 3.4. Дискретные отсчеты сигнала

 

Поскольку теорема отсчетов (теорема Котельникова) сформулирована для сигнала с ограниченным спектром, а реальные сигналы имеют неограниченную спектральную плотность, то при расчетах Дt=1/(2Fmax) используют приближенное значение Fmax(например, активную ширину спектра, определенную по амплитудному критерию, по критерию 90%-ного содержания энергии или средней мощности сигнала). Кроме того, и идеальный фильтр низких частот, необходимый для восстановления сигнала в соответствии с теоремой, явля­ется физически нереализуемым, так как предъявляемые к нему требования (идеально прямоугольная форма ампли­тудно-частотной характеристики, отсутствие фазового сдвига в рассматриваемой полосе частот от 0 до Fmax) оказы­ваются противоречивыми и могут выполняться лишь с определенной погрешностью. Учитывая сказанное, частоту дискретизации по времени обычно принимают в 1,5–2,5 раза больше значения, рассчитанного по теореме Котельникова, т.е.

 

fдискр = (3 – 5)Fmax.

 

Существуют и другие способы выбора частоты дискрети­зации сигнала (с учетом времени корреляции передаваемого сообщения, значения наибольшего или среднеквадратичного отклонения процесса и т. д.). Так, в соответствии с критерием Н.А.Железнова, который выполняется для случайных сигналов, имеющих конечную длительность Тси неограни­ченный частотный спектр, рекомендуется принимать шаг дискретизации Дt, равный максимальному интервалу корре­ляции сигнала ф0. Предполагается, что параметр ф0, характеризует такой промежуток времени, в пределах которого отдельные значения случай­ного процесса можно считать статистически зависимыми (коррелированными), причем ф0“Тс. Таким образом, исход­ный непрерывный сигнал заменяется совокупностью N = Тс/ф0некоррелированных отсчетов (импульсов), следующих с частотой fдискр=1/Дt=1/ф0. При этом восстановление сигнала x(t) осуществляется с помощью линейного прогнози­рующего фильтра со среднеквадратической ошибкой, сколь угодно мало отличающейся от нуля в промежутке времени, равном интервалу корреляции ф0.

Более полно учитывая свойства реальных сигналов (ко­нечная длительность, неограниченность спектра), критерий Железнова тем не менее исходит из допущения о равенстве нулю корреляционной функции сигнала Kx(ф) вне интервала [–ф0; ф0], что на практике выполняется с определенной погрешностью.

В тех случаях, когда имеется более подробная инфор­мация о законе изменения сигнала, выбор частоты дискре­тизации можно осуществлять исходя из допустимой погреш­ности аппроксимации функции x(t) на каждом из интер­валов дискретизации. На рис. 3.5 дан пример кусочно-линейной аппроксимации, когда соседние отсчеты функции x(t), взятые в дискретные моменты времени ti, и ti+1, сое­диняются отрезками прямых.

 

Рис. 3.5. Кусочно-линей­ная аппроксимация

 

Рассмотренные способы равномерной дискретизации (при Дt = const) иногда могут приводить к получению избыточ­ных отсчетов, не оказывающих существенного влияния на процесс восстановления исходного сообщения. Например, если функция x(t) мало изменяется на некотором, доста­точно протяженном интервале времени Т0, то соответствующие дискретные отсчеты сигнала практически не отличаются друг от друга и, следовательно, нет необходимости использовать все указанные отсчеты для хранения или передачи информации по линии связи. Сокращение избыточной информации возможно на основе способов адаптивной (неравномерной) дискретизации, обеспечивающих выбор интервала Дt между соседними отсчетами с учетом фактического изменения характеристик сигнала (в частности, скорости его изменения).

Квантование (дискретизация) сигнала по уровню – процесс отображения бесконечного множества значений аналогового сигнала на некоторое конечное множество (определяемое числом уровней квантования).

Отличительной особенностью дискретизации по уровню является замена непрерывной шкалы уровней сигнала x(t) дискретной шкалой xд.i(I = 1, 2,...,m), в которой различные значения сигнала отличаются между собой не менее чем на некоторое фиксированное (или выбираемое в процессе квантования) значение Дx, называемое шагом кванто­вания.

Шаг квантования – величина, равная интервалу между двумя соседними уровнями квантования (определена только для случая равномерного квантования).

Необходимость квантования вызвана тем, что цифровые вычислительные устройства могут оперировать только с числами, имеющими конечное число разрядов. Таким образом, квантование представляет собой округление передаваемых значений с заданной точностью. При равномерном квантовании (Дx=const) число разрешенных диск­ретных уровней xiсоставляет:

 

где xmaxи xmin– соответственно верхняя и нижняя границы диапазона изменения сигнала.

Ошибка квантования – величина, определяемая как ж(х) = x – xд.i, где x – кодируемая дискретная величина, xд.i– дискретизированный сигнал.

Шум квантования – случайная функция времени, определяемая как зависимость ошибки квантования от времени.

Чем меньше значение Дx, тем меньше получаемая ошибка. Если в результате квантования любое из значений сиг­нала х(t), попавшее в интервал (хд.i – Дх/2; хд.i + Дх/2), округ­ляется до хд, то возникающая при этом ошибка ж(х) не превышает половины шага квантования, т.е. max|ж(х)|=0,5Дx. На практике шаг квантования Дx выбирают исходя из уровня помех, в той или иной форме присут­ствующих при измерении, передаче и обработке реальных сигналов.

Если функция x(t) заранее неизвестна, а шаг квантова­ния Дх достаточно мал по сравнению с диапазоном изме­нения сигнала (xmax–xmin), то принято считать ошибку квантования ж(х) случайной величиной, подчиняющейся равномерному закону распределения. Тогда, как показано на рис. 3.6, плотность вероятности f1(ж) для случайной величины ж, принимает значение 1/(Дх) внутри интервала (–Дх/2; +Дх/2) и равна нулю вне этого интервала. В дан­ном случае дисперсию D[ж] ошибки квантования ж, нахо­дят как

 

Рис. 3.6. Равномерный закон распределения ошибки кван­тования

 

При Дх=const относитель­ная погрешность квантования дx=ж(х)/x существенно зависит от текущего значения сигнала x(t). В связи с этим при необ­ходимости обработки и переда­чи сигналов, изменяющихся в широком диапазоне, нередко используется неравномерное (нелинейное) квантование, ког­да шаг Дх принимается малым для сигналов низкого уровня и увеличивается с ростом соответствующих значений сигнала (например, Дх выбирают пропорционально логарифму значения |x(t)|). Выбор шага Дхi=xд.i–xд.i-1осуществляется еще и с учетом плотности распределения случайного сигнала (для более вероятных значений сигнала шаг квантования выбирают меньшим, для менее вероятных – большим). Таким образом удается обес­печить высокую точность преобразования при ограниченном (не слишком большом) числе разрешенных дискретных уровней сигнала x(t).

Процесс преобразо­вания дискретного сигнала в цифровой называют коди­рованием информации, а множество различных кодовых комбинаций, получаемых при данном правиле кодирова­ния, – кодом. Важной характеристикой кода является осно­вание (или значность) кода m, т. е. число возможных зна­чений, которые могут принимать элементы кодовой комбинации. Пусть требуется передать сигнал, уровень которого изменяется от 0 до 10 В. Если шаг квантования данных составляет 10 мВ, то каждый отсчет сигнала можно рассматривать как одно из 1000 возможных сообщений. Для передачи этой информации можно предложить различные способы:

а) каждому сооб­щению поставить в соответствие определенный уровень напряжения, при этом основание кода m=1000, а длина кодовой комбинации (слова) принимает минимальное значение n=1;

б) можно воспользоваться двоичным (бинарным) представлением амплитуды сигнала с m=2, но тогда потребуется комбинация длины n=10 (210=1024, так что некоторые комбинации здесь не использованы).

Примером двоичного кода является запись натурального числа А в позиционной двоичной системе счисления, осу­ществляемая по следующему правилу:

 

Здесь символы а1, а2, …, anпринимают значения 0 или 1, n – число разрядов в коде. Предполагается, что символ a1, расположенный в старшем разряде кодовой комбина­ции, имеет наибольший вес 2n-1, тогда как вес символа anв младшем разряде является минимальным и равен 20=1.

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

 

,

 

т. е. веса разрядов кодовой комбинации а1, а2, …, anздесь равны 2-1, 2-2,..., 2-n. В тех случаях, когда число А может принимать очень большие или же очень малые значения, удобнее использовать представление числа в форме с плавающей запятой. При этом каждое десятичное число определяется мантиссой, принимающей дробные значения от 0,1 до 1, и порядком – показателем степени числа 10. Например, число 50 представляется как 0,5·102, а число 0,00105 записывается в виде 0,105·10-2. Соответственно представление в двоичном коде для числа А должно про­изводиться отдельно – для мантиссы и для порядка числа А.

Возможны и промежуточные варианты. Поэтому целесообразно поставить вопрос об определении оптимальной пары значений m и n.

В качестве критерия оптимальности S примем минимум произведения числа требуемых символов (уровней) m на длину кодовой комбинации n, необходимой для представле­ния заданного числа сообщений N. Тогда можно записать

 

S=min(mn)=min(m log2N/ log2m)

 

3.3. Системы счисления. Методы перевода чисел из одной системы счисления в другую

 

3.3.1. Основные понятия

 

Система счисления – совокупность приемов и правил для записи чи­сел цифровыми знаками или символами.

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

 

Таблица 3.1