обычно называют -двоично-десятичными системами или двоично-десятичными кодами. Как следует из функции >(5), при 5=10 минимальное количество двоичных разрядов, с помощью которых можно получить однозначное кодирование всех десяти цифр десятичной системы равно четырем. Поэтому имеет смысл рассматривать только тот случай, когда q>4, в основном мы ограничимся случаем, когда каждый Ацесятичный разряд в записи числа заменяется группой из четырех двоичных разрядов. Эти четверки двоич-

ных разрядов мы будем называть тетрадами.

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

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

Требования, которым должно удовлетворять двоично-десятичное кодирование, при намерении использовать двоично-десятичную систему в вычислительной машине были впервые полностью сформулированы Рутисхаузером. Рутисхаузер потребовал, чтобы дво-

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

1. Требование единственности. Каждой десятичной цифре должна взаимно однозначно сопоставляться некоторая двоичная тетрада. Выполнение этого требования необходимо для возможности работы с двоично-десятичным представлением и эффективности процесса декодирования.

2. Требование упорядоченности. Большим десятичным цифрам должны соответствовать большие двоичные тетрады. Возможно выполнение противоположного требования: большим десятичным цифрам должны соответствовать меньшие тетрады. Необходимость выполнения этого требования связана с вы-

полнением в двоично-десятичном представлении операции сравнения.

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

4. Требование дополнительности. Если десятичные цифры а,- и Uj таковы, что а,- + Uj = 9, то, если цифре сопоставлена тетрада mjnmm,20яо. должна быть сопоставлена тетрада щтттп, в которой Ml получается из тга заменой нуля на единицуи единицы на нуль. Выполнение требования дополни"-тельности необходимо для возможности введения в двоично-десятичной системе аналогов дополнительного и обратного кодов, используемых при операции алгебраического сложения.

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

ai = miPi + mp + msPs + niiPi. , (5.5)

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

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

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

торые мы изучаем, обязательно обладают свойством единственности. При q двоичных разрядах число различных кодов,- которые можно записать в этих разрядах, равно 2. Если при данном способе кодирования мы используем только L кодов из этого множества, то говорят, что используемый код имеет длину L. Таким образом, при кодировании цифр q двоичными разрядами длина кода заключена в пределах 1 < Z. < 2. Число различных кодов длины L оценивается как

л, = • . * - (5.6)

• i2<-L)\

Свойства кодов, удовлетворяющих требованию весо-мозначности, были исследованы И. Клиром. Им же была получена полная таблица всех весомозначных кодов при q = 4 длины десять. Как следует из соотношения (5.6), общее число кодов с такими параметрами равно 16!: 6! Однако большинство из этих кодов не является весомозначными. Для нахождения всех весомозначных кодов рассмотрим. некоторые свойства, которым такие коды должны удовлетворять.

. Прежде всего условимся в дальнейшем, что веса, сопоставляемые разрядам, упорядочены так, что PinPk-> номер разряда больше номера разряда k, т. е. . -

Теорема 5.3. Для всех весов справедливо неравенство

Pk<--

Доказательство. Из условия упорядоченности весов по величине следует, что теорему необходимо доказать лишь для веса Pg i, стоящего в левом старшем разряде. Сначала рассмотрим случай, когда все веса являются положительными и = 2~ -f- г. Тогда для всех чисел х< 2~-f-г-f-1 соответствующие им двоичные коды должны иметь в старшем разряде цифру нуль. Но в {q - 1)-м разряде при двоичном кодировании можно получить только 2" различных комбинаций. Таким образом, г не может быть положительным числом.- Для случая положительных весов теорема доказана. - .