Например, в алфавите А = {а, 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
