И А Кулик, Е М Скородина, С В Костель - Генерирование кодов-сочетаний для решения информационных задач иус - страница 1

Страницы:
1  2  3  4 

УДК 519.714 : 621.391

И.А. КУЛИК, Е.М. СКОРДИНА, С. В. КОСТЕЛЬ

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

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

1. Введение

Во многих информационно-управляющих системах (ИУС) достаточно большие объемы информации составляют данные, представленные последовательностями, сумма элемен­тов которых не превосходит или равна некоторой величине, т.е. кодами-сочетаниями. Генерирование таких последовательностей и приписывание им номеров позволяет прово­дить не только их эффективное кодирование, но и существенно облегчить решение задач целочисленного программирования, в которых генерирование или перечисление допустимо­го множества векторов является довольно трудной задачей.

Информационные задачи, распространенные в ИУС, в том числе комбинаторных, воз­можно решать более эффективно, используя коды-сочетания и предлагаемые в этой работе способы их получения. К ним относятся задачи сбора, коммутации, хранения и передачи данных, адаптации параметров и принятия оптимальных управленческих решений. Более того, одни и те же ограничения соответствуют одновременно и монотонным числовым последовательностям, и комбинаторным сочетаниям, тем самым расширяя область воз­можного эффективного применения кодов-сочетаний на задачи вычислительной обработки данных [1, 2].

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

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

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

Приведенное ниже исследование основывается на установленном в работе [5] положе­нии, что в структуре комбинаторных объектов можно обнаружить соответствующие им структурные числа. В частности, для кодов-сочетаний такими структурными числами являются биномиальные числа.

Цель предлагаемой работы - снижение временных и стоимостных затрат при выполне­нии характерных для ИУС информационных задач: хранениея и передача данных, оптими­зация процессов обработки информации и принятие управленческих решений.

Для достижения указанной цели необходимо решить следующие задачи:

- выделить в структуре кодов-сочетаний двоичные биномиальные числа;

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

Поставленные задачи следует рассматривать с точки зрения комбинаторного кодиро­вания кодов-сочетаний ввиду следующего обоснования.

1. Коды-сочетания представляют собой последовательности, на значения весовых ха­рактеристик и расположение элементов которых накладываются ограничения. Вследствие этого операциям кодирования и декодирования кодов-сочетаний придается комбинаторный характер [1, 6].

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

3. Комбинаторные ИУС достаточно широко распространены и разрабатываемые по сути комбинаторные модели и методы генерирования и перечисления кодов-сочетаний должны органично войти в математическое и алгоритмическое обеспечение таких инфор­мационных систем [1, 7].

2. Предварительные сведения

Комбинаторное решение сформулированных в работе задач представляет собой разра­ботку методов комбинаторного кодирования множества Y кодов-сочетаний, имеющих заданное ограничение RY. Это означает установление взаимно-однозначного отображе­ния f:Y F между последовательностями Yj єY и элементами множества F = {0,1,...,| Y | -1} целых неотрицательных чисел Fj є F . В рамках комбинаторного коди­рования рассматриваются три задачи: подсчета, перечисления и генерирования [1, 8].

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

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

Двоичные биномиальные числа Xj =( x^..^..^ ) генерируются двоичной биномиаль­ной системой счисления, обладающей числовой функцией вида:

Fj=i>iCk-:\ (1)

и системами ограничений для образования множества X чисел Xj, Xj є X , j = 0, N -1:

q = k        Jl = n - k

xr = 1 и [ xr = 0 , (2) где n и k - целочисленные параметры двоичной биномиальной системы счисления; r -количество разрядов биномиального числа, r < n ; Xi - биномиальная двоичная цифра Xi є {0,1}; q - число единиц в биномиальном числе; qi - сумма единичных Xi, начиная с первого разряда числа до (i -1) -го включительно:

i-1

qi = Z xt, (3) t=1

здесь q1 = 0 , qi < k ; N =     - количество двоичных биномиальных чисел Xj.

3. Связь решаемых задач с параметрами ИУС

В рамках временных и стоимостных характеристик реализации задач ИУС, связанных с кодами-сочетаниями, можно выделить составляющие, отвечающие за генерирование, пе­речисление и обработку рассматриваемых кодов:

T = т    +T     V = v    + V

ксч       ксч'  *        ксч *ксч'

где T и V - время и объем аппаратно-программных затрат для решения типовой инфор­мационной задачи соответственно; тксч и - время и объем аппаратно-программных затрат соответственно, требуемых на генерирование, перечисление и обработку кодов-сочетаний; Тксч и - время и объем аппаратно-программных затрат для решения

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

Tmin = min Тксч + Тксч , Vmin = min vксч + Vксч .

В качестве примера ИУС, в которой задействованы коды-сочетания, можно привести систему контроля ошибок на основе t -SEC/AUDE кодов, где t - минимальное граничное полурасстояние (half-distance) между двумя произвольными кодовыми комбинациями. Дан­ная система, с одной стороны, обнаруживает все асимметричные ошибки, которые харак­терны для работы электронных устройств, а с другой - обнаруживает и исправляет все однократные симметричные ошибки, которые возникают в основном при передаче по каналам связи. Для формирования t -SEC/AUDE кодов широко используются коды-соче­тания как с одним весом, так и с двумя [10].

Аналогично увеличение производительности при разрабатываемом подходе будет на­блюдаться и для ИУС распределения частот передачи в сетях радиосвязи, в том числе мобильной связи стандарта GSM. Для формирования списков распределения частот радио­передатчикам также эффективно можно использовать коды-сочетания [11].

4. Модели процессов генерирования и перечисления кодов-сочетаний

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

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

Определение. Отображение f: X Y называется биномиальным, если его область определения X или область Y значений составляют биномиальные числа.

Определив соответствие G с X хY, (Xj,Yj G, между множествами X двоичных биномиальных чисел и Y кодов-сочетаний, тем самым задачи пересчета и генерирования кодов-сочетаний Yj сведем к аналогичным задачам, но уже для биномиальных чисел Xj. Обратно, построив соответствие Z с X х Y, (Yj,Xj Z, решение задачи перечисления кодов-сочетаний Yj будем основывать на результатах решения этой же задачи, но для двоичных биномиальных чисел Xj. С учетом существования числовой функции (1) и систем ограничений (2) для биномиальных чисел Xj, которые являются числообразующи-ми, решение таких задач на основе предложенного подхода потребует заметно меньшего объема вычислительных и временных затрат. Очевидно, с точки зрения однозначностикодирования и декодирования кодов-сочетаний соответствия G и Z должно быть функци­ональными и определять прямую Ф и обратную ф-1 функции перехода от биномиальных чисел Xj к кодам-сочетаниям Yj и обратно от Yj к Xj. В свою очередь, нахождение функций Yj =ф( Xj) и Xj =ф-1 (Yj) означает построение биективных биномиальных ото­бражений ф:X    Y и ф- :Y X.

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

1) перечисление кодов-сочетаний Yj с заданным ограничением Ry в целях получения их номеров Fj:

Fj= f (Yj[ Ry ]) = у(ф-1 (Yj [Ry ])) ; (4)

2) генерирование кодов-сочетаний Yj с заданным ограничением Ry на основе соответ­ствующих номеров Fj:

1 Yj [Ry ] = f-1 (Fj ) = ф(у-1 (Fj)); (5)

где у: X F и у : F X - биективные прямое и обратное отображения множества X биномиальных чисел Xj на множество F номеров Fj и обратно F на X соответственно.

Следует отметить, что отображения у и у 1 могут быть реализованы с использовани­ем числовой функции (1) и систем ограничений (2) [5, 9].

В графическом виде модели процессов перечисления и генерирования кодов-сочетаний Yj є Y [Ry ] представлены на рисунке.

Код-сочетание

Обратное биномиальное отображение вида

ф-1 :Y[RY ] — X[n,k]

Биномиальное число X j

Прямое

 

биномиальное

Номер Fj

отображение вида у :X[n,k] — F

 

 

 

Номер Fj

Обратное биномиальное отображение вида

у-1^ — X[n,k]

Биномиальное число Xj

Прямое биномиальное отображение вида

ф :X[n,k] — Y[ Ry ]

Код-сочетание

Yj

б

Модели процессов: а - перечисления; б - генерирования кодов-сочетаний

От задач перечисления и генерирования кодов-сочетаний общего вида перейдем к частному случаю, когда требуется получение отдельного вида сочетаний - квазиравновес­ных комбинаций Yj =(y1y2...yi...yn-1) с весовым распределением количества единиц k -1, k , где 1 < k < n -1. При этом ограничение Ry будет иметь вид вектора, состоящего из двух компонентов k-1 и k :

Ry =(k - 1,k), k = xVi.

i=1

Прямое и обратное биномиальные отображения ф:X[n,k] Y[(k- 1,k)) и ф-1 :Y[(k- 1,k))—» X[n,k] для квазиравновесных кодов-сочетаний Yj =(y1y2...yi...yn-1) и двоичных биномиальных чисел Xj = (x1X2...Xi...xr) длины min(k,n-k)<r<n-1 с пара­

Страницы:
1  2  3  4 


Похожие статьи

И А Кулик, Е М Скородина, С В Костель - Генерирование кодов-сочетаний для решения информационных задач иус