Алгоритмы формирования кодов - сочетаний на основе многозначных биномиальных чисел

АЛГОРИТМЫ ФОРМИРОВАНИЯ КОДОВ - СОЧЕТАНИЙ НА ОСНОВЕ МНОГОЗНАЧНЫХ БИНОМИАЛЬНЫХ ЧИСЕЛ

Онанченко Е.Л., канд. техн. наук, доц.; Белан М.Ю., студ.; Онанченко А.Е., студ.

В статье идет речь об алгоритмах формирования комбинаторных кодов на основе биномиальной системы счисления с многозначным алфавитом. С помощью соответствующих алгоритмов начальный десятичный номер преобразован в число многозначной биномиальной системы счисления, потому что эта структура соответствует структуре комбинационных кодов. Следовательно, это число преобразовано в комбинаторную конфигурацию. Обратная проблема решена. Работа алгоритмов иллюстрирована примером.

ВВЕДЕНИЕ

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

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

Второй, не менее важной проблемой, является проблема достоверности информации, так как появление ошибок может привести к тяжелым последствиям. Источниками ошибок в системе передачи информации являются помехи в линиях связи, отказы в аппаратуре, действия обслуживающего персонала. Требования к вероятности искажения информации с каждым годом ужесточаются [3].

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

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

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

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

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

ПОСТАНОВКА ЗАДАЧИ

Построение комбинаторных кодов целесообразно производить с использованием систем счисления, структура которых близка к структуре порождаемых ею кодов. Широко распространенные системы счисления, использующие в качестве основания показательные функции, например, двоичная, не позволяют генерировать комбинаторные коды с использованием простых и надежных алгоритмов. Существенно упростить алгоритмы генерирования комбинаторных кодов позволяют системы счисления, основанием которых являются биномиальные коэффициенты, получившие название биномиальные системы счисления [1].

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

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

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

РЕЗУЛЬТАТЫ

Переход от многозначных биномиальных чисел к сочетаниям может происходить с помощью приведенных ниже алгоритмов, построенных на основе ряда теорем [2].

Теорема 1 Если б₁ б₂…б_i…б_k - многозначное число, то если к каждой б_j-й цифре этого числа прибавить индекс цифры, уменьшенный на единицу (i-1) , и сумму цифр числа, предшествующих ей при счете слева направо, то полученная цифра

(1)

является элементом последовательности, которая образует сочетание В=в₁в₂…в_i…в_k.

Доказательство Так как мощность множеств многозначных биномиальных чисел вида А = б₁ б₂…б_i…б_k и сочетаний В = в₁ в₂…в_i …в_k одинакова, то достаточно показать, что отображение f, заданное формулой (1), инъективно. Другими словами, разным многозначным числам А₁ и А₂ ставятся в соответствие различные сочетания

В₁ = f(A₁) = в₁…в_k и В₂=f(A₂)=в'₁…в'_k.

В самом деле, пусть А₁ = б₁ б₂…б_i…б_k и А₂ = б'₁ б'₂…б'_i…б'_k - два различных числа, то есть А₁?А₂. Пусть далее r ? 1 - первый слева разряд, в котором А₁ отличается от А₂, то есть

б_i = б'_i, i = 1, …r-1 , (2)

б_r = б'_r . (3)

Необходимо показать, что тогда аналогичные соотношения имеют место для В₁ и В₂. Действительно, из правила (1) и соотношений (2) - (3) вытекают цепочки:

,

которые и означают, что В₁ = f (A₁) ? В₂ = f (A₂).

Алгоритм перехода от многозначного биномиального числа к соответствующему сочетанию будет иметь следующий вид:

1 Первая цифра сочетания равна старшей цифре многозначного биномиального числа.

2 Для следующей цифры биномиального числа вычисляется сумма Si-1 предыдущих цифр при счете слева направо.

3 Вычисляется соответствующая цифра сочетания

. (4)

4 Пункты 2, 3 повторяются до тех пор, пока не будет получена последняя k-я цифра сочетания.

Пример 1 Биномиальное число 3020 преобразовать в сочетание:

в₁ = б₁ = 3;

В результате получено сочетание - 3478.

Теорема 2 Если б₁ б₂…б_i…б_k является многозначным биномиальным числом, то если к каждой б_i-й цифре этого числа, кроме старшей, прибавить единицу и предшествующий в_i-1, полученный при счете слева направо элемент новой последовательности, причем в₀=0, то полученный элемент -- в_i= б_i+1+ в_i-1 _ образует последовательность, которая будет сочетанием в₁ в₂ …в_k.

Алгоритм преобразования многозначных биномиальных чисел в сочетания из n элементов по k имеет следующий вид:

1 Первая цифра сочетания равна старшей цифре биномиального числа.

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

3 Пункт 2 повторять до тех пор, пока не будет получена последняя k -я цифры сочетания. Останов.

Пример 2 Биномиальное число 3020 преобразовать в сочетание:

в₁ = б₁ = 3;

в₂ = б₂ +1+ в₁ = 0+1+3=4;

в₃ = б₃ +1+ в₂ = 2+1+4=7;

в₄ = б₄ +1+ в₃ = 0+1+7=8.

В результате получено сочетание - 3478.

Из примеров 1 и 2 видно, что в результате преобразования одного и того же биномиального числа по двум различным алгоритмам получены одинаковые сочетания.

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

Теорема 3 Если б₁ б₂…б_i…б_k является сочетанием с повторением цифр, то если к каждой б_i-й его цифре прибавить индекс и отнять единицу, то полученная цифра - в_i = б_i+i-1 _ является элементом последовательности, которая образует сочетание в₁ в₂ …в_k.Алгоритм перехода от сочетания с повторением к соответствующему сочетанию будет иметь следующий вид:

1 Вычисляется цифра сочетания, начиная со старшей, равная сумме цифры сочетания с повторением и ее индекса.

2 2 Пункт 1 повторяется до тех пор, пока не будет получена последняя k-я, цифра сочетания. Останов.

Пример 3 Сочетание с повторением 1125 преобразовать в сочетание:

в₁ = б₁ + i - 1= 1+1-1=1;

в₂ = б₂ + i - 1= 1+2-1=2;

в₃ = б₃ + i - 1= 2+3-1=4;

в₄ = б₄ + i - 1= 5+4-1=8.

В результате получено сочетание - 1248.

Обратное преобразование при переходе от комбинаторной конфигурации к двоичному слову происходит следующим образом: комбинаторная конфигурация - биномиальное число - двоичное слово.

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

Теорема 4 Если в₁ в₂ …в_i …в_k - сочетание и если от каждой, кроме первой, в_i цифры сочетания отнять предыдущую при счете слева направо цифру сочетания и единицу, а первая цифра равна старшей цифре сочетания, то полученная цифра

б_i = в_i - в_i-1 - 1 (5)

является элементом последовательности, которая образует многозначное биномиальное число б₁ б₂…б_i…б_k.

Доказательство. В силу равномощности множества многозначных биномиальных чисел и сочетаний с повторениями достаточно установить инъективность функции q, которая ставится в соответствие каждому сочетанию, многозначное биномиальное число А = q (В) по формуле (5). Рассмотрим два различных сочетания В₁ = в₁ в₂ …в_k и В₂ = в'₁ в'₂ …в'_k и покажем, что тогда q (В₁) = q (В₂). Пусть f ? 1 - первый слева разряд, в котором эти сочетания различаются, то есть

в₁= в'₁ , i=1,…, f-1, (6)

в₁? в'_f . (7)

Так как в₁= в'₁ по определению (5), то из (6) и (7) вытекают цепочки соотношений:

б_i = в_i - в_i-1 - 1 = в'_i - в'_i-1 - 1 = б'_i , i=1,…, f-1,

б_f = в_f - в_f-1 - 1 ? в'_f - в'_f-1 - 1 = б'_f ,

из которых делаем вывод, что A₁= f (В₁) ? A₂ = f (В₂). Теорема доказана.

Алгоритм преобразования сочетания в многозначное биномиальное число имеет следующий вид:

1 Старшая цифра многозначного биномиального числа равна первой цифре сочетания.

2 Вычисляется следующая цифра многозначного биномиального числа

б_i =в_i - в_i-1 - 1.

3 Пункт 2 повторять, пока не будет получена младшая цифра многозначного биномиального числа.

Пример 4 Преобразовать сочетание 3478 в многозначное биномиальное число:

б₁ = в₁ = 3;

б₂ =в₂ - в₁ - 1=4-3-1=0;

б₃ =в₃ - в₂ - 1=7-4-1=2;

б₄ =в₄ - в₃ - 1=8-7-1=0.

Получено многозначное биномиальное число 3020, что подтверждает правильность перевода многозначного биномиального числа в сочетания и обратно.

Сочетания представляют собой сжатую форму записи равновесного кодового слова, так как:

- количество цифр в сочетании определяет количество единиц в равновесной кодовой комбинации (k=4);

- разрядность равновесного кода определяется соотношением n=k+q, т. е. всего n-разрядов от нулевого до (n-l)-гo;

- значения цифр сочетания являются адресами единиц в равновесных кодовых комбинациях.

Поэтому коды _ сочетания удобно применять для формирования равновесных кодовых слов.

ВЫВОДЫ

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

Достоинством применения ЭВМ является универсальность преобразований, но значительные затраты машинного времени являются серьезным недостатком. В случаях, когда имеются жесткие ограничения на время преобразования либо требуется простое недорогое устройство с ограниченным объемом возможных преобразуемых кодовых комбинаций, то предпочтение отдается специализированным преобразователям, построенным на жесткой логике. Появление не дорогих ПЛИС позволяет расширить область применения специализированных преобразователей.

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

SUMMARY

The article deals with algorithms of forming of combined code on binary system of numeration with multiciphered alphabet. With the help of corresponding algorithms the initial decimal number is transformed into the number of binary system of numeration, because this structure corresponds to the structure of combined code. Consequently this number is transformed into combinatory configuration. The inverse problem is solved. The work of algorithms is illustrated by example.

СПИСОК ЛИТЕРАТУРЫ

1 Борисенко А.А., Онанченко Е.Л., Кобяков А.Н. Системы счисления с биномиальным основаним // Вестник Сумского государственного университета. - 1994. _ № 1.- С.96-101.

2 Онанченко Е.Л., Протасова Т.А. Алгоритмы формирования комбинаторных кодов на основе многозначных биномиальных чисел // Вісник Сумського державного університету. - 1996. _ № 1(5). - С.84-88

3 Советов Б. Я., Стах В. М. Построение адаптивных систем передачи информации для автоматизированного управления. - Л.: Энергоиздат, Ленинградское отделение, 1982. -120 с.