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

Представление натурального числа N в виде (5.9.14) называют p -кодом Фибоначчи числа N. Сокращенная запись p -кода Фибоначчи .

Выражение (5.9.14) включает в себя теоретически бесконечное число способов нумерации натуральных чисел, так как каждому классу эквивалентности соответствует свой p -код Фибоначчи. Рассмотрим крайние частные случае p -кода Фи­боначчи.

Пусть р = 0. В этом случае p -числа Фибоначчи совпадают с двоичными числами, т.е. , и выражение (5.9.14) принимает вид

. (5.9.15)

Пусть р = ¥. В этом случае каждое p -число Фибоначчи тождественно равно 1, т.е. для любого , и выражение (5.9.14) принимает вид унитарного кода N = l + l +... + l.

Рассмотрим структуру отображения множества двоичных слов на множество натуральных чисел в p -коде Фибоначчи при р > 0. Пример для 5-разрядных двоичных слов при р =1 и 2 представлен ниже:

p = 0 p = 2

Здесь можно усмотреть следующие особенности кодирова­ния натуральных чисел.

1. При заданных целых и помощью -разрядного р -кода Фибоначчи можно представить натуральных чисел от 0 до включительно. В приведенном примере от 0 до 12 и от 0 до 8 соответственно для р = 1 и 2.

2. Имеется множественность представления чисел при р > 0, за исключением числа 0 и максимального числа , равного 12 при р = 1 и п = 5 или 8 при р = 2 и n = 5, все остальные натуральные числа имеют множественное кодовое представление, т.е. каждому числу соответствует некоторое множество кодовых представлений.

3. Множественное кодовое представление имеет зеркально-инверсную ось симметрии. Так, для приведенного примера при р = 1 для числа 1 имеем А ₁ = А ₃₀и А ₂ = А ₂₉, для числа 3 имеем А ₅ = А ₂₆, А ₆ = А ₂₅, A ₈ = A ₂₃ и т.д.

Далее, наборы А, лежащие на оси симметрии, также зеркально-инверсно симметричны между собой:

для числа 6 имеем А ₁₃ = А ₁₈, А ₁₄ = А ₁₇ (при p = 1);

для числа 4 имеем А ₁₁ = А ₂₀, A ₁₃ = A ₁₈, А ₁₄ = А ₁₇ (при р = 2).

5.9.4. Код золотой p -пропорции

Коды золотой p -пропорции по своим математическим свойствам близки к p -кодам Фибоначчи. Эта близость следует из математической связи между p -числами Фибоначчи и золотой p -пропорцией. Было показано, что отношение p -чисел Фибоначчи (т.е. отношение весов соседних разрядов в p -коде Фибоначчи) при неограниченном увеличении их номеров стремится к золотой p -пропорции . Предел отношения весов соседних разрядов в p -коде Фибоначчи можно считать основанием указанного способа нумерации натуральных чисел, что позволяет с определенной степенью условности p -коды Фибоначчи отнести к классу систем счис­ления с иррациональными основаниями .

Сходство между упомянутыми кодами состоит также в су­ществовании одной и той же математической зависимости между весами двоичных разрядов рассматриваемых кодов. Это позволяет к p -кодам Фибоначчи и кодам золотой р- пропорции применять одни и те же правила преобразования кодовых изображений.

Вместе с тем имеется различие между p -кодами Фибоначчи и кодами золотой p -пропорции. Во-первых, p -коды Фибоначчи предназначены для представления натуральных чисел, в то время как коды золотой p -пропорции – для представления действительных чисел. Во-вторых, веса разрядов кода золотой p -пропорции в отличие от весов разрядов p -кода Фибоначчи образуют геометрическую прогрессию. Это имеет практическое значение при реализации такой важной арифметической опера­ции, как сдвиг кода.

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

В основу построения алгоритма метрологического кодирования положена математи­ческая процедура проверки отношения эквивалентности (§ 5.4), которая описывается двумя соотношениями: в виде набора шкал

(5.10.1)

и как отображение через отношение эквивалентности

, (5.10.2)

где – итерационный алгоритм выбора меры; – шаг алгоритма; S_g = l при x > 0, S_g = 0 при x = 0, S_g = -1 при х < 0.

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

5.10.1. Алгоритм Стахова

Для построения оптимального n -шагово­го алгоритма цифрового кодирования опишем следующую математическую модель физического измерения.

Основной измерительной процедурой при аналоговом измерении для АЦП является операция «сравнение свойств». На языке модели кодирования эта операция заключается в разбиении исходного отрезка АВ, численно равного диапазону преобразования аналогового сигнала, в определенном отноше­нии. Результат же сравнения состоит в проверке отношения эквивалентности.

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

(5.10.3)

где и – сравниваемые свойства.

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

Систему формальных правил разбиения отрезка АВ при помощи компаратора при определенных ограничениях W называется (п, k, W)-алгоритмом цифрового метрологического ко­дирования (ЦМК).

Описанный алгоритм ЦМК, по-существу, сведен к одномер­ному поиску координаты точки X на отрезке АВ с помощью k компараторов за п шагов. Ясно, что на последнем шаге действия алгоритма выделяется некоторый интервал неопреде­ленности , содержащий точку X. Рассматривая действие алгоритма для всех точек Х Î АВ и выделяя все интервалы неопределенности, содержащие соответствующие точки X, полу­чаем множество интервалов неопределенности. Особый интерес представляют случаи, когда (п, k, W)-алгоритм разбивает отре­зок АВ на N равных интервалов. В этом случае при равновероятности распределения точек Х Î АВ количество ин­формации, содержащееся в процедуре цифрового метрологического кодирования, будет , где D – наименьшая точность определения точки X, численно равная числу уровней квантования, и задача синтеза оптимального (п, k, W)-алгоритма сводится в этом случае к нахождению (п, k, W)-алгоритма, обеспечивающего наиболь­шее число уровней квантования N.

В технике аналого-цифрового преобразования широкое рас­пространение получили следующие алгоритмы ЦМК:

1. Последовательного счета, в котором за п шагов отрезок АВ с помощью одного компаратора разбивается на п + 1 равных частей, т.е.

; (5.10.4)

2. Поразрядного кодирования, в котором за п шагов отрезок АВ с помощью одного компаратора разбивается на 2 ⁿ равных частей, т.е.

; (5.10.5)

3. Считывания, состоящего из одного шага (n = l), при этом с помощью k компараторов отрезок АВ разбивается на k + l равных частей, т.е.

. (5.10.6)

Описанные выше математические модели ЦМК распростра­няются только на такие АЦП, в которых функционирование устройства сравнения (компаратора) описывается двухаргументной функцией (5.10.3). За рамки этой модели выходят АЦП считывания, использующие двоично-кодированные рефлексные коды, например код Грея. В основе двоично-кодированных шкал лежит более сложный тип компаратора, который является многоаргументным.

5.10.2.Фибоначчиевы алгоритмы цифрового метрологического

кодирования

Обозначим через F_p (n) – функцию, разбивающую отрезок АВ на n равных интерва­лов единичной длины, т.е. AB = F_p (n). Следует заметить, что алгоритмы функционирования и структурные схемы АЦП в кодах Фибо­наччи и золотой пропорции ничем принципиально не отлича­ются от алгоритмов и структурных схем АЦП в классическом двоичном коде. Рассматриваемые ниже алгоритмы относятся к числу алгоритмов поразрядного кодирования. Однако положенные в основу этих алгоритмов ЦМК соотношения, связывающие веса двоичных разрядов, придают АЦП в кодах Фибоначчи и золотой пропорции ряд новых качественных свойств.

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

1. п £ р + 1. В этом случае после первого шага кодирования в распоряжении алгоритма остается п -1 шагов, а так как р ³ п - 1, то кодирование фактически заканчивается после первого шага. Рекуррентная формула для вычисления функции F_p (n)имеет вид

(5.10.7)

Введем следующее определение:

(5.10.8)

Раскладывая в (5.10.7) по той же рекуррентной формуле п раз, с учетом (5.10.8) получаем

(5.10.9)

Переходя к системе мер, заметим, что оптимальная система мер в этом случае состоит из п единичных мер {1, 1, 1,..., 1}, а оптимальный n -шаговый алгоритм кодирования заключается в том, что на каждом шаге кодирования очередная единичная мера прибавляется до тех пор, пока сравниваемая величина больше суммы мер. И этот процесс продолжается либо до исчерпания всех мер, либо до получения нулевого результата сравнения. Указанный алгоритм кодирования, как уже упомина­лось, широко распространен в технике аналого-цифрового преобразования под названием алгоритма последовательного счета.

2. п > р + 1. В этом случае рекуррентная формула для вычисления функции F_p(n) имеет вид

(5.10.10)

Объединяя (5.10.7), (5.10.9) и (5.10.10), получаем следующую рекуррентную формулу для вычисления функции F_p (n) в общем случае:

(5.10.11)

Для перехода к системе шкал с соответствующими мерами введем обозначения: – мера старшей шкалы; – мера младшей шкалы. Тогда при п > р + 1 система мер для реализации оптимального n -шагового алгоритма кодирова­ния будет определяться последовательностью , причем первые (р + 1) мер имеют единич­ный вес, т.е.

, (5.10.12)

а каждая последующая мера , где l > р, вычисляется по рекуррентной формуле

. (5.10.13)

Можно показать, что между функцией F_p (n) задаваемой выражением (5.10.11), и функцией задаваемой выражениями (7.10.12), (7.10.13), существует следующая связь:

. (5.10.14)

Другими словами, функция F_p (n) есть сдвиг последователь­ности вправо на р цифр р -ряда Фибоначчи.

Таким образом, при заданном р ³ 0 оптимальный n -шаговый алгоритм ЦМК с помощью системы мер осуществляет разбиение отрезка АВ на равных интервалов единичной длины. Можно показать, что при заданном р оптимальная система мер задается с помощью р -чисел Фибоначчи. Поэтому описанные выше алгоритмы ЦМК называют фибоначчиевыми алгоритмами.

Рассмотрим частные случаи этих алгоритмов. Пусть р = 0. В этом случае система мер является двоичной, а фибоначчиевый алгоритм совпадает с алгоритмом поразрядного кодирования.

Пусть р = ¥. В этом случае система мер состоит из единичных мер {1, 1,..., 1}, а фибоначчиевый алгоритм совпа­дает с алгоритмом последовательного счета.

Пример 5.10.1. Зададимся р = 1 и рассмотрим поведение n -шагового фибоначчиевого алгоритма на отрезке АВ. Для этого вычислим значения функций F ₁(n) и по рекуррентным формулам (5.10.11) ¸ (5.10.14):

N
F 1(n)

Оптимальный n -шаговый алгоритм кодирования разбивает отрезок АВ на F ₁(n) частей; это осуществляется с помощью системы мер , ,..., . Пусть необходимо закодировать 5 разрядов. В этом случае 5-шаговый алгоритм кодирования разбивает отрезок АВ на F ₁(5) = 13 частей, при этом используется система из 5 мер: 1, 1, 2, 3, 5. Рассмотрим первые два шага указанного 5-шагового алгоритма кодирования, действующего на отрезке [0, 13].

Первый шаг. Компаратор прикладывается к точке 5 и разбивает отрезок [0, 13] в «фибоначчиевом» отношении 5 + 8 (рис. 5.10.1, а).

Второй шаг. Если компаратор показал «вправо» (код 1), то интервал неопределенности сужается до отрезка [5, 13] в «фибоначчиевом» отношении 3 + 5 (рис. 5.10.1, б).

Если компаратор показал «влево» (код 0), то интервал неопределенности сужается до отрезка [0, 5] (рис. 5.10.1, в) и на втором шаге запрещается прикладывать компаратор к точкам отрезка [0, 5]. В этом случае при приложении компаратора к точке 2 отрезок [0, 5] разбивается в «фибоначчие­вом» отношении 2 + 3 (рис. 5.10.1, в).

Рис. 5.10.1. Пример фибоначчиевого алгоритма кодирования

Последующие шаги " фибоначчиевого" алгоритма аналогичны первым двум шагам и состоят в разбиении интервалов неопределенности каждый раз в " фибоначчиевом" отношении.