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

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

Таким образом, развитие предложенной идеи заключается в следующем: принимать начальное состояние решетки блочного клеточного автомата за первый из N базисных векторов, после чего каждый новый вектор, соответствующий очередному состоянию развития клеточного автомата, проверять на взаимную ортогональность с уже найденными векторами. Однако количество состояний в отдельно взятой истории развития клеточного автомата с учетом наличия дополнительных клеток в решетке может составлять до |А|^-2(т-1), вследствие чего необходимо ввести ограничение на число просматриваемых состояний. Будем считать, что история развития клеточного является «неперспективной», если к моменту времени t„ < < |А|Л' — 2С"11) было найдено меньше Nn попарно взаимно ортогональных векторов, 1 ^ iVn < N, причем значения tn и N„ для клеточного автомата к-го порядка с решеткой из N клеток могут быть подобраны экспериментальным путем.

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

Алгоритм, реализующий все вышесказанное, представлен ниже.

Вход:

натуральное N ^ 2;

натуральное т ^ 2, причем N = 0(mod т) и гп ф N

отрезок ряда неотрицательных целых чисел А {0,1,2,..., /—1}, причем log2к 6 Z;

вектор-строка S = (s^)|’_1) s, € {0, ..., rn — 1};

2 lm

матрица : (фу)гк1 )=1, фцAm причем fp,q выполняется фр Ф Фч при р Ф q:

/“чО / — 1) _ а

вектор-строка С = (с*) •_ 1 , с* 6 А;

вектор-строка В Ы 6 Z или Q;

натуральное Ап, 1 ^ Ап < А;

натуральное 1ц, N ^ tn ^ lA^-2^-1).

Выход:

возврат матрицы С (c»j)f f j j, строки которой представляют собой элементы искомого базиса, либо сообщение о невозможности его построения при заданном наборе входных данных.

  • 1. Для г от гпдо т + N — 1 выполнить:
  • 1.1. С1^_т+1 Ьсо+1.

  • 2. Полагаем t ?*— 1, N' 2.
  • 3. Пока N' ^ N, выполнять следующее:
  • 3.1. Если t tn и N' — 1 < АД, то история развития клеточного автомата считается «неперспективной» и алгоритм заканчивается неудачей. В противном случае перейти к следующему шагу.
  • 3.2. Полагаем s st(modr).
  • 3.3. Если s = 0, то вычислить а <— т — 1 и d <— 0, иначе

вычислить а <— s 1 и d +— 1.

  • 3.4. Для г от 1 до N/m + d выполнить:
  • 3.4.1. Для такого и, что щи = (c‘^m+s, c‘+1im+s+i,

^a+im+s+m—1) ПОЛаГЛСМ (^а-Мтег-Мр ^a-bim-r+ 1? ???> l) ^ Ф^и ?

  • 3.5. Для i от m до m + N — 1 выполнить:
  • 3.5.1. c;,i_m+1 <— bct+1.

i

3.6. Если для всех значений i от 1 до N имеем = сл,

то цикл завершился и алгоритм заканчивается неудачей.

В противном случае перейти к следующему шагу.

  • 3.7. Для i от 1 до N' — 1 выполнить:
  • 3.7.1. Полагаем х 0.
  • 3.7.2. Для j от 1 до N выполнить:
  • 3.7.2.1. Вычислить х <— х + CijCffj.
  • 3.7.3. Если 1^0, то вычислить t <— t + 1 и перейти к

шагу 3.1.

  • 3.8. Вычислить N' <— N' + 1 и перейти к шагу 3.
  • 4. Возврат (С).

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >