Минимум этой функции находится в той точке, где значение производной dcldb = О. Таким образом, имеем

; (infe)

производная равна нулю, когда Infe = 1, т.е. Ь=е.

Не очень удовлетворительный результат. Так как е = 2.71828, наиболее эффективными основаниями систем счисления являются 2 и 3. Какое из них более эффективно? Отношение стоимости регистра при использовании основания 2 к стоимости регистра при использовании основания системы счисления, равного 3, таково:

с(2) k-2log,(M н-1) 21п(У1/ +1)/(1п2) 21пЗ с(3) k-2log3{M+l) 31п(Л/+1)/(1пЗ) 31п2

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

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

ГЛАВА 13 КОД ГРЕЯ

13.1. Построение кода Грея

Нельзя ли циклически перебрать все 2" комбинаций из и битов путем изменения при каждой итерации только одного бита? Ответ на этот вопрос - "да"; и именно это свойство определяет коды Грея (Gray codes). Итак, код Грея - это такой способ кодирования целых чисел, при котором закодированное число и число, следующее за ним, отличаются только одним битом. Эта концепция может быть обобщена для любого основания системы счисления, например для десятичных чисел, но в этой главе рассматриваются только бинарные коды Грея.

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

Отраженный двоичный код Грея строится следующим образом. Начинаем со строк О и 1, которые представляют соответственно целые числа О и 1.

Возьмем отражение этих строк относительно горизонтальной оси после приведещюго списка и поместим 1 слева от новых записей списка, а слева от уже имевшихся разместим 0.

00 01 И 10

Таким образом получен отраженный код Грея для и=2. Чтобы получить код для и=3, повторим описанную процедуру и получим

ООО 001 011 010 НО 111 101 100

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

При л > 2 существуют нецикличесьсие коды Грея, которые состоят из всех 2" значений, взятых по одному разу. Примером такого кода может служить следующий: ООО 001 ОН 010 110 100 101 111.

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

Рис. 13.1. Четырехбитовый код Грея и формулы преобразования

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

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

• Бит i числа в коде Грея представляет собой четность бита / и бита слева от него в соответствующем двоичном числе (если слева от бита i нет битов, используем значение 0).

• Бит / двоичного числа представляет собой четность всех битов в позиции / и слева от нее в соответствующем числе кода Грея.

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

f "

G<-B® B»l .

Преобразование кода Грея в двоичное число существенно сложнее: