К определению свойств унитарной системы счисления

АВТОРЕФЕРАТ ДИССЕРТАЦИИ

К ОПРЕДЕЛЕНИЮ СВОЙСТВ УНИТАРНОЙ СИСТЕМЫ СЧИСЛЕНИЯ

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

Введение и постановка задачи

При разработке и построении преобразователей формы информации важным есть определение метода кодирования, который позволяет эффективно реализовать системные функции информационной технологии [1 - 4]. Информация в цифровых системах представляется в дискретной форме. Результаты анализа процедур преобразования формы информации позволили определить, что на начальном этапе преобразование аналоговой информации в цифровых информационных системах в большинстве случаев осуществляется в унитарный код с последующим его преобразованием в системы счисления с уменьшенной разрядностью, например, двоичную, Грея, Галуа или другие [2]. При этом также различают такие типы преобразования информации, как позиционирование в пространстве и в виде перемещений (рис. 1).

Поскольку унитарное кодирование есть базовым, это определило необходимость исследования основ формирования унитарных кодов. Определение метода унитарного кодирования, которое имеется в литературных источниках на сегодняшний день [3 - 8], в полной мере не отвечает современным требованиям к построению преобразователей формы информации, поэтому решение задач исследования унитарного кодирования и построения эффективных преобразователей формы информации с его применением представляется актуальным.

Анализ унитарной системы счисления

Результаты исследований, в том числе и проводимых авторами, позволили определить, что унитарная система счисления относится к однородным степенным позиционным системам [1 - 3, 5 - 7]. Они в общем случае описываются следующим уравнением:

N = a_n-1q^n-1 + a_n-2q^n-2 +…+ a_iqⁱ +…+ a₁q¹+ a₀q⁰ = a_i qⁱ; (1)

где а_i - цифра алфавита A={0, 1, … q-1}; q - основание системы счисления,

i=0, …, n-1 - позиция в разрядной сетке кодовой комбинации (числа).

Соответственно унитарный код записывается как

N = a_n-11^n-1 + a_n-21^n-2 +…+ a_i1ⁱ +…+ a₁1¹+ a₀1⁰, (2)

В нем основание q=1, а цифра a_i согласно (1) и того, что алфавит а_i =0, … q-1 может быть формально идентифицирован исключительно одним кодовым символом - нулем. Тогда выражение (2) формально принимает следующий вид:

N=0*1^n-1 + 0*1^n-2 +…+ 0*1ⁱ +…+ 0*1¹+ 0*1⁰=0. (3)

Из полученного значения N=0 можно ошибочно предположить, что такую систему счисления нельзя использовать на практике. Однако это не так. В унитарной системе счисления в качестве информационного признака используется не значение N=0, а число разрядов j, представляющих N=0, которое изменяется от 1 до n. Поэтому согласно (3), число формально закодировано не только символом нуля, но и любым числом унитарных символов. Чтобы соблюсти принятую логику формирования бинарных информационных потоков, заменим формальный унитарный знак нуля согласно определению (3) на знак единицы, что не есть ошибкой и не нарушает изложения (2), которое после указанной формальной замены примет следующий вид:

N = 1*1^j +…+ 1*1¹+ 1*1⁰=j. (4)

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

Синхронизация унитарных кодов

Характер унитарного формирования, передачи, обработки и архивирования унитарных информационных сообщений требует их синхронизации, поэтому каждое возможное число унитарных символов (разрядов кода) необходимо отделять от следующего числа специальным разделяющим знаком, отличным от знаков информационной посылки [1, 5, 9]. Например, если в качестве знаков информационной посылки выступают единицы, то в качестве разделяющего знака можно принять ноль (см. табл.1).

Таблица 1

Характер формирования префиксного унитарного кода

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

Оптимизация распределения неравновероятных сообщений

В силу неравномерности длин комбинаций унитарного кода он может быть оптимизирован для определенного распределения вероятностей формирования сообщений [1, 9]. В таком распределении сообщения с большей вероятностью формирования могут кодироваться комбинациями меньшей длины и, соответственно, с меньшей вероятностью - комбинациями большей длины. Так, если заданы вероятности сообщений p₁, p₂, …, p_j, …, p_n, такие, что p₁ > p₂ > … > p_j> … > p_n, то им следует установить в соответствие кодовые комбинации длины l₁, l₂, …, l_j, …, l_n,, для которых l₁, < l₂, < …, < l_j, < …, < l_n. Это будет оптимальный код в отношении минимального объема формируемых сообщений и максимальной скорости передачи информации. Средняя длина кодовых комбинаций, которая определяется выражением:

, (5)

будет минимальной. В соответствии с теоремой Шеннона эта длина будет приближаться к энтропии сообщения. Покажем это на следующем примере. Для распределения длин в диапазоне l_j = 0, …, 10 кодовых элементов с неодинаковыми значениями вероятностей формирования сообщений, приведенными на рис. 2 и сведенными в таблице 2 параметр средней длины примет значение:

_опт.=1*0,19+2*0,17+3*0,15+4*0,13+5*0,11+6*0,09+7*0,07+8*0,05+9*0,03+10*0,01 =

= 0,19 + 0,34 + 0,45 + 0,52 + 0,55 + 0,54 + 0,49 + 0,4 + 0,27 + 0,1 =3,85 ,

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

Рисунок 1 - Гистограмма оптимизированного распределения вероятностей сообщений.

Таблица 2

Распределение длин кодов для разных значений вероятностей формирования неравновероятных сообщений

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

_max.= 10*0,19+9*0,17+8*0,15+7*0,13+6*0,11+5*0,09+4*0,07+3*0,05+2*0,03+1*0,01 =

= 1,9 + 1,53 + 1,2 + 0,91 + 0,66 + 0,45 + 0,28 + 0,15 + 0,06 + 0,01 =7,15 .

Рисунок 2 - Гистограмма наихудшего распределения вероятностей сообщений.

При неравновероятном формировании сообщений для оценки энтропии источника используется формула Шеннона:

H=, (6)

согласно которой

H = 0,19*2,4 + 0,17* 2,56+ 0,15*2,74 + 0,13*2,94 + 0,11*3,18 + 0,09*3,47 + 0,07*3,84 + + 0,05*4,32 + 0,03*5,06 + 0,01*6,64 = = 0,456 + 0,4352 + 0,411 + 0,3822 + 0,3498 + 0,3123 + 0,2688 + 0,216 + 0,1518 + 0,0664 = = 3,0495

Соответственно, количество информации при равновероятном формировании признаков в унитарном коде, будет равняться log₂n = 3,32.

Таким образом, результаты сравнения значений оптимальной _опт.=3,85 и максимально возможной _max.=7,15 средней длины кодовых комбинаций со значением энтропии источника сообщений H = 3,05 позволяют обосновать эффективность применение предложенного метода оптимизации неравновероятных распределений.

Избыточность унитарного кодирования

Характерным свойством унитарной системы счисления есть значительная избыточность, которая с одной стороны требует соответственных вычислительных мощностей, но положительным свойством которой есть повышение помехоустойчивости передачи-приема информационных сообщений на базе определения и коррекции ошибок [1 - 4, 6, 9]. Используя теорему Хартли, выражение для определения избыточности R унитарного кодирования можно представить выражением

R=2^j/j=2^j-1, (7)

из которого следует, что такое преобразование характеризуется максимальной для известных методов кодирования избыточностью, значение которой R возрастает в экспоненциальной зависимости от длины j унитарной кодовой последовательности. На базе формулы (7) произведена оценка избыточности R для различных значений j, результаты которой сведены в таблице 3, а на рисунке 4 изображены соответствующие графические зависимости.

Таблица 3

Значения избыточности унитарного кода

Рисунок 3 - Оценка Хартли избыточности унитарного кодирования.

Оценка достоверности информационного обмена

Построение технических средств преобразования формы и цифровой обработки информации с заданной разрядностью шины данных требует определения состояния всех разрядов шины. Характеристической особенностью формирования в информационных системах унитарного кода есть его представление в виде набора импульсов, кодируемых группами логических нулей/единиц, среди которых нет единиц/нулей [1, 2, 9]. Появление единицы/нуля среди них свидетельствует об ошибке. Используя критерий D оценки достоверности Хартли в общем виде для бинарных кодов, который определяет долю обнаруживаемых ошибок,

D=1-M/K (8)

где M - число разрешенных комбинаций в коде, K=2^j - число возможных кодовых комбинаций, получим следующее выражение для унитарного кода:

D=1-1/K=1-1/2^j, (9)

из которого для заданных конкретных значений j результаты представлены в таблице 4.

Таблица 4

Достоверность информационного обмена на базе унитарного кодирования.

Выводы

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

Литература

Борисенко А.А. Дискретная математика - Суми: Університетська книга, 2008. - 255 с.

Петришин Л.Б. Теоретичні основи перетворення форми та цифрової обробки інформації в базисі Галуа. - Київ: ІЗіМН МОУ, 1997. - 237 с.

Самсонов Б. Б., Плохов Е. М., Филоненков А. И., Кречет Т. В. Теория информации и кодирования. - Ростов-на-Дону: Феникс, 2002. - 287 с.

Морес-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. Техносфера, 2005. - 317 с.

Панин В.В. Основы теории информации. - М.: Бином, 2007. - 436 c.

Самсонов Б.Б. Плохов Е.М. Филоненков А.И. Компьютерная математика (основание информатики). - Ростов-на-Дону: Феникс, 2002. - 512 c.

Сырецкий Г.А. Информатика: Фундаментальный курс: Т. 2: Информационные технологии и системы. - СПб: БХВ-Петербург, 2007. - 848 c.

Кнут Д. Э. Искусство программирования для ЭВМ. Т. 2. - М.: Вильямс, 2001. - 832 с.

Борисенко А.А. Биномиальные автоматы.- Сумы: Изд-во СумГУ, 2005. - 121 с.

До визначення властивостей унітарної системи числення. Здійснено аналіз унітарного числення, що дозволило віднести унітарну систему до класу однорідних степеневих позиційних систем. Визначено та здійснена оцінка таких основних властивостей, як нерівномірність коду та метод його оптимізації, надлишковість і достовірність унітарного кодування.

To definition of properties of a unitary numbering system. The analysis of unitary numbering is realized, whose results made it possible to carry unitary system to the class of homogeneous exponential position systems. They are determined and is made an evaluation of such basic properties as the nonuniformity of the code and the method of its optimization, redundancy and the authenticity of unitary coding.