Математика \ Дискретная математика

Задача о кодировании. Задача о генерировании, страница 3

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

Например, применяя этот метод к рассмотренной выше конкретной булевой матрице X, мы выбираем сначала строку 1, а затем добавляем к ней строку 2. Покомпонентная дизъюнкция этих строк представляется вектором

0101001,

задающим разбиение множества столбцов напримерноравные части.

Очевидно, что последующее добавление к совокупности {1, 2} какой-либо из остальных строк не повысит различающую способность соответствующей дизъюнкции. Поэтому совокупность {1, 2} принимается в качестве первого элемента искомого теста.

Следующие элементы конструируются аналогичным образом, причем их качество оценивается теперь количеством разбиваемых ими пар столбцов, принадлежащих различным блокам разбиения, порождаемого уже включенными в тест элементами. Так находятся совокупности {3, 5} и {3, 6}, определяющие последние две строки следующего трехэлементного дизъюнктивного теста, оказывающегося минимальным:

Отображая выбранные совокупности строкиз матрицы Х соответствующими строками операторнойматрицыВи используя в качестве матрицы Y полученнуюматрицу дизъюнктивного теста, мы найдемоптимальное решение данной задачи о кодировании матрицы X:


Поиск минимальной троичной кодирующей матрицы. Сформулируем аналогичную задачу над уравнением Y = ТÑХ, интерпретируя ее как задачу нахождения минимальной троичной кодирующей матрицы Т для заданной входной булевой матрицы X.

Сравнивая эту задачу с предыдущей, установим следующее ее отличие: элементами обобщенного теста становятся теперь дизъюнкции не только строк матрицы X, но также их инверсий. В связи с этим напрашивается следующий метод решения новой задачи, сводящий ее к старой: добавив в матрицу Х отрицания всех строк, расширить ее таким образом до матрицы X*, а затем решать задачу о кодировании для уравнения Y=BÑX*. Полученная матрица Y будет удовлетворять обоим уравнениям, а матрица Т легко получается из матрицы В попарной сверткой ее столбцов. При этом каждая сворачиваемая пара соответствует такой паре строк в матрице X*, которые представляют некоторую строку из Х в прямой и инверсной форме. «Прямые» строки отображаются при свертке единицами, «инверсные» — нулями.

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

Исходя из этих соображений, а также с целью сокращения объема вычислений при поиске обобщенного теста, можно рекомендовать -ограничить число строк в матрице X*, сравняв его с числом строк в исходной матрице Х и положив, что хi* = хi, если относительная доля единиц в строке х, не превышает половины, и что хi* =не(хi) в противном случае.

Допустим, например, что

и требуется найти минимальные по числу строк матрицы Y и Т, удовлетворяющие уравнению Y = ТÑХ.

Начнем решение задачи с построения матрицы X*, в которой минусом отмечены строки, полученные инверси-рованием соответствующих строк матрицы X:

— и будем теперь рассматривать уравнение Y == ВÑХ*, применив к нему изложенный выше метод решения задачи о кодировании.

Скачать файл