Построение ортогонального базиса на основе псевдослучайных последовательностей

Задача обеспечения помехоустойчивого кодирования в системах цифровой передачи информации остается и будет еще долго оставаться весьма актуальной. Снижение вероятности передачи ошибочных бит позволяет снижать мощности передающих устройств, уменьшать габариты систем. Особенно это актуально в системах, допускающих определенную вероятность ошибки передачи, не влияющую на потребительское качество получаемой информации. В системах передачи изображений [1][2][3], например, можно допустить определенные искажения, не влияющие на их восприятие. В таких системах применяют протоколы сжатия и помехоустойчивое кодирование на основе ортогональных преобразований с кусочно-постоянными базисными функциями [4][5][6]. Несмотря на простоту и понятность использования таких преобразований, они обладают и рядом недостатков. В качестве основного можно привести неравномерное распределение энергии по базису преобразования, что приводит к существенным пульсациям энергии в канале передачи.

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

Исходной информацией для построения ПСП является образующий многочлен

где a_N, a₁ = 1; a_i ∈ {0,1}; N – число разрядов регистра сдвига.

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

Любому образующему полиному можно поставить в соответствие генератор Фибоначчи [7]

где g_i(t) – состояние i-го разряда регистра сдвига на такте 

В матричном виде алгоритм формирования последовательности будет

Рассмотрим пример.

M(x) = x³ + x² +1.

В соответствии с (2) можно записать:

Или в матричном виде:

Таблица состояний разрядов регистра, построенная в соответствии с (4) и (5), приведена ниже.

Таблица

Состояния разрядов регистра сдвига

Как видно из таблицы, полный цикл последовательности состоит из 8 тактов, 7 из которых не повторяются, 8-й такт является началом нового периода. ПСП снимается с разряда g₃. Ее период равен 2^N – 1, N – число разрядов.

Рассмотренные последовательности обладают следующими свойствами.

1. Период ПСП, формируемый в соответствии с образующим полиномом M(x), равен

M = 2^{N – 1} (6)

2. Для заданного M(x) существует M различных ПСП, полученных путем цикличного сдвига исходной последовательности.

3. Число единичных символов на периоде ПСП равно 2^{N – 1}, а нулевых 2^{N – 1} – 1.

4. В ПСП серии из одного символа встречаются 2^{N – 2} раз, из двух одинаковых символов – 2^{N – 3} раз и так далее. Серии из N – 1 нулей и N единиц присутствуют только один раз.

5. Автокорреляционная функция полученной последовательности определяется выражением:

6. Децимация последовательности по четному индексу j = M – 1 приводит к инверсии исходной последовательности, которая соответствует последовательности, порождаемой полиномом M^–1(x), обратным M(x). {b_i} = {c_–i}, где b_i – инверсная ПСП, c_i – прямая.

Рассмотренные ПСП принято называть последовательностями максимального периода, или М-последовательностями.

Количество различных полиномов M(x) порождающих М-последовательность, зависит от ее периода M = 2ⁿ – 1. Оно быстро возрастает с увеличением n. Для n = 8 количество порождающих полиномов равно 16 [8]. Конкретный вид получаемой последовательности будет зависеть еще и от начальных условий, заданных для инициализации формирования последовательности. При n = 8 количество начальных условий равно 255. Таким образом, при заданном n = 8 количество разновидностей М-последовательностей составляет 16 (2ⁿ – 1) ≈ 4000. С увеличением n это число быстро возрастает (при n = 10, например, до 60 000).

Таким образом, используя механизм формирования [7] последовательностей максимального периода, можно построить достаточно большое количество ортогональных преобразований, которые можно использовать для преобразования сигналов при передаче их по каналам связи [9].

Рассмотрим процесс формирования матрицы преобразования. Как следует из свойства 2, необходимое количество строк матрицы может быть получено путем цикличного сдвига исходной последовательности. Количество строк в такой матрице будет равно периоду M = 2ⁿ – 1, и матрица будет иметь размер M × M. Все строки и столбцы данной матрицы будут представлять собой М-последовательности. Пример формирования такой матрицы представлен на рисунке 1а. Данная матрица обладает свойством симметричности строк и столбцов в соответствии со свойством 5. Автокорреляционная функция при совпадающих строках и столбцах равна 1. Однако при несовпадении строк и столбцов значение автокорреляционной функции равно –1/M. Результат произведения матрицы M на M^T, где M^T – транспонированная матрица, приведен на рисунке 1б. Результат умножения не является единичной матрицей, что не соответствует признакам ортогонального преобразования.

Для выполнения условий ортогональности необходимо:

• выровнять количество нулевых и единичных символов на периоде ПСП, сделав его равным 2ⁿ – 1;
• внести знакопеременность в ПСП для обеспечения нулевой постоянной составляющей в строках и столбцах матрицы.

Сформированная таким образом матрица преобразования M⁸₀ и соответствующее ей произведение на транспонированную M^8T₀  приведены на рисунке 2.

Рис. 1. Матрица получения сдвигом влево последовательности при M(x) = x³+x²+1 и начальном состоянии 100(4) (а) и результат умножения на транспонированную матрицу (б)

Рис. 3. Использование ортогонального преобразования для передачи спутникового изображения по каналу с шумами: исходное изображение (а), результат воздействия шумов (СКО = 40) при передаче без преобразования (б) и результат передачи с преобразованием (СКО = 2,55) (в)

Как видно из рисунка 2, матрица M⁸₀, построенная для примера, приведенного выше, соответствует требованиям ортогональности и может быть использована для преобразования сигналов. Количество таких матриц зависит от необходимого числа n и соответствует количеству М-последовательностей, которые могут быть построены на основе разнообразных образующих полиномов. В общем случае можно записать пару преобразования:

где Fⁿ_c – матрица (матрица-строка) коэффициентов преобразования сигнала; Bⁿ_c – матрица (матрица-столбец) сигнала; Mⁿ₀^T – транспонированная матрица преобразования.

На рисунке 3 представлен результат использования данного подхода для моделирования процесса передачи спутниковых изображений [10][11][12] по каналу связи. Образующий полином M(x) = x⁷+ x⁵+ x⁴+ x³+1, начальное состояние 10101101(173). В качестве сигнальной матрицы Bⁿ_c выступает матрица яркостей изображения. Поскольку матрица M₀ – симметричная, то в операции транспонирования необходимости нет.

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