СИСТЕМА ДЛЯ СЖАТИЯ ДВУХМЕРНОГО МАССИВА ИНФОРМАЦИИ Российский патент 1995 года по МПК G08C15/06 

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

Известно устройство [1] позволяющее эффективно сжимать двумерные массивы информации лишь в случае существования элементов массива, мало отличающихся по строке и/или столбцу. Наиболее близким к изобретению является устройство для сжатия двумерного массива информации [2] обеспечивающее получение более высокого коэффициента сжатия, чем упомянутое выше устройство. Эффект большего сжатия в этом устройстве достигнут благодаря использованию регрессионной модели второго порядка в качестве средства приближенного описания данных, содержащихся в двумерном массиве. Оно содержит блок сокращения избыточности по строкам и столбцам, формирователи (постоянные запоминающие устройства) коэффициентов регрессионного сжатия по строкам и столбцам и синхронизатор. Блок сокращения избыточности по строкам и столбцам содержит шесть одинаковых блоков формирования элементов выходного массива, обеспечивающих умножение элементов входного массива на коэффициенты регрессионного сжатия по строкам и столбцам и накопление шести сумм произведений, являющихся элементами выходного массива информации. При этом информация, содержащаяся во входном массиве размерностью n₁ x n₂ элементов, передается с помощью шести чисел. Максимальная размерность n₁ x n₂ входного массива, который может быть сжат с помощью этого устройства, определяется степенью сложности и монотонности двумерной зависимости, соответствующей этому числовому массиву. Формирователи элементов выходного массива, входящие в состав блока сокращения избыточности, содержат каждый два умножителя и два накапливающих сумматора.

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

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

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

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

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

Рассмотрим сжатие двумерного массива информации T_ijТ (X_1i, X_2j), содержащего N (2n₁ + 1)(2n₂ + 1) чисел, где 2n₁ + 1 количество чисел в строке массива; 2n₂ + 1 количество чисел в столбце массива; X_1i i, -n₁ ≅ i ≅ n₁; X_2j j, -n₂ ≅ j ≅ n₂.

Рассмотрим полиномиальную регрессионную модель М-го порядка:
(X₁, X₂)b_klXk1

Xl2= b₀₀+b₁₀X₁+b₀₁X₂+b₀₂X21++b_omXM2
Для определения коэффициентов регрессии b_kl воспользуемся методом наименьших квадратов. Тогда система уравнений для вычисления коэффициентов имеет вид
C_b d, (1) где С Х^тХ; d Х^тТ;
b искомый столбец коэффициентов b_kl;
d столбец правых частей d_kl нормальной системы уравнений.

Матрица С симметрична и ее порядок равен числу базисных функций модели, т.е.

L (M+1)(M+2)
Для вычисления элементов этой матрицы требуется примерно LN LN операций умножения. Однако для полиномиальной модели в случае равномерной сетки можно построить алгоритм, в котором число операций не зависит от числа узлов сетки, а определяется лишь порядком модели М.

Матрица С имеет не более L различных элементов вида
А_kl= A_k⁽¹⁾A_l⁽²⁾; 0=≅k+l≅M,(2) где A(k

¹⁾= X2k1i; A(l²⁾= X2l2j; 0≅ l≅ M 0≅k≅M
Коэффициенты вида A_k и A_l определяются из рекуррентных формул:
A_k= (3) где F_o 2n + 1; ε n (n + 1);
F_k= ε^kF_o- F_k-S . (4) Имеем A_o 2n + 1; ε n (n + 1); (5)
3A₁ ε A_o;
5A₂ ε ²A_o A₁;
7A₃ ε ³A_o 5A₂;
9A₄ ε ⁴A_o 14A₃ A₂;
11A₅ ε ⁵A_o 30A₄ 7A₃;
13A₆ ε ⁶A_o 55A₅ 27A₄ A₃ и т.д.

Полагая n n₁ и ε ε₁, находим коэффициенты A_k⁽¹⁾, при n n₂ и ε ε₂ определяем коэффициенты A_l⁽⁷⁾, после чего путем перемножения найденных коэффициентов определяем остальные M (M-1) коэффициентов A_kl.

Показано, что при подходящей нумерации базисных функций модели матрица коэффициентов нормальной системы является клеточно-диагональной:
C и расщепляется на четыре независимых системы с матрицами коэффициентов С⁰⁰, С¹⁰, С⁰¹ и С¹¹. В каждой из этих систем нумерация коэффициентов регрессии b_kl и правых частей d_kl совпадает с нумерацией диагональных элементов A_kl соответствующей матрицы коэффициентов:
C d_iag (C⁰⁰, C¹⁰, C⁰¹, C¹¹), (6) что приводит к расщеплению нормальной системы (6) на четыре независимых подсистемы:
C⁰⁰B⁰⁰ D⁰⁰; C⁰¹B⁰¹ D⁰¹;
C¹⁰B¹⁰ D¹⁰; C¹¹B¹¹ D¹¹. (7)
Порядки клеток отдельных матриц связаны с числом базисных функций L и порядком модели М соотношениями
L P⁰⁰+P¹⁰+P⁰¹+P¹¹ Если М четное, то
P⁰⁰= (M+2)(M+4);
P¹⁰= P⁰¹=P¹¹= M(M+2). Если М нечетное, то
P¹¹= (M²-1)
P⁰⁰= P¹⁰= P⁰¹= (M+1)(M+3) Для М ≅ 6 порядки клеток приведены в таблице.

Для определения элементов матрицы С моделей меньших порядков применяется следующий алгоритм. Пусть заданы одномерные массивы q (0 10 210 3210 43210 543210 6543210) h (0 01 012 0123 01234 0123456) Тогда
С_rs⁰⁰ A_kl; 1 ≅ r₁s ≅ P⁰⁰;
C_rs¹⁰ A_k+1,l; 1 ≅ r₁s ≅ P¹⁰;
C_rs⁰¹ A_k,l+1; 1 ≅ r₁s ≅ P⁰¹;
C_rs¹¹ A_k+1,l+1; 1 ≅ r₁s ≅ P¹¹, где k g_r + g_s; l h_r + h_s.

В качестве примера выпишем верхнюю треугольную часть клеток матрицы С для модели шестого порядка:
A₀₀A₁₀A₀₁A₂₀A₁₁A₀₂A₃₀A₂₁A₁₂A₀₃
A₂₀A₁₁A₃₀A₂₁A₁₂A₄₀A₃₁A₂₂A₁₃
A₀₂A₂₁A₁₂A₀₃A₃₁A₂₂A₁₃A₀₄ C⁰⁰ A₄₀A₃₁A₂₂A₅₀A₄₁A₃₂A₂₃ (8)
A₂₂A₁₃A₄₁A₃₂A₂₃A₁₄
A₀₄A₃₂A₂₃A₁₄A₀₅
A₆₀A₅₁A₄₂A₃₃
A₄₂A₃₃A₂₄
A₂₄A₁₅
A₀₆
A₁₀A₂₀A₁₁A₃₀A₂₁A₁₂
A₃₀A₂₁A₄₀A₃₁A₂₂ C¹⁰ A₁₂A₃₁A₂₂A₁₃ (9)
A₅₀A₄₁A₃₂
A₃₂A₂₃
A₁₄
A₀₁A₀₂A₁₁A₀₃A₁₂A₂₁
A₀₃A₁₂A₀₄A₁₃A₂₂ C⁰¹ A₂₁A₁₃A₂₂A₃₁ (10)
A₀₅A₁₄A₂₃
A₂₃A₃₂
A₄₁
A₁₁A₂₁A₁₂A₃₁A₂₂A₁₃
A₃₁A₂₂A₄₁A₃₂A₂₃ C¹¹ A₁₃A₃₂A₂₃A₁₄ (11)
A₅₁A₄₂A₃₃
A₃₃A₂₄
A₁₅
При использовании МНК наибольшее количество операций требуется для вычисления правых частей d_kl:
d_klXk1

_iXl2_jT_ij (12)
Двойная сумма может быть преобразована к повторной сумме
Skj^o=Xk1_iT_ij; -; (13)
S_j^kl S_j^koX_2j^l; O ≅ k + l≅ M;
n ≅ j ≅ n₂; (14)
d_kl= Skj^l, 0 ≅ k+l≅ M. (15)
Это позволяет сократить число операций умножения при вычислении правых частей с 2NL до NM + (2n₂ + 1)L и облегчает задачу обработки данных в темпе их поступления по строкам массива Т.

Решив четыре независимых системы уравнений, находим коэффициенты регрессии
B⁰⁰ (C⁰⁰)^-1 D⁰⁰;
B⁰¹ (C⁰¹)^-1 D⁰¹;
B¹⁰ (C¹⁰)^-1 D¹⁰; (16)
B¹¹ (C¹¹)^-1 D¹¹;
B⁰⁰= ; B¹⁰; B⁰¹= B¹¹= (17)
Если потребителей информации несколько и требования к точности восстановления данных по сжатой информации различны, возможно представление сжатых данных как комбинации коэффициентов регрессионной модели и массива корректирующих данных, так и только коэффициентов регрессионной модели. В последнем случае коэффициент сжатия максимален, а точность восстановления минимальна.

На фиг. 1 изображена блок-схема системы для сжатия двумерного массива информации; на фиг. 2 схема блока сокращения избыточности; на фиг. 3 схема формирователя группы коэффициентов правых частей нормальной системы; на фиг. 4 схема постоянного запоминающего устройства (ПЗУ) коэффициентов регрессионного сжатия по строкам, столбцам и ПЗУ коэффициентов обратной матрицы; на фиг. 5 схема блока формирования сжатых данных; на фиг. 6 схема вычислителя группы коэффициентов регрессионной модели; на фиг. 7 схема накопителя суммы попарных произведений; на фиг. 8 схема блока восстановления; на фиг. 9 схема блока формирования корректирующих данных; на фиг. 10 схема синхронизатора; на фиг. 11-13 временная диаграмма работы системы для сжатия двумерного массива информации; на фиг. 14 схема делителя частоты по модулю Р; на фиг. 15-17 и 18 схемы регистров, используемых в синхронизаторе.

Система для сжатия двумерного массива информации (фиг. 1) включает источник 1 информации, дискретизатор 2, аналого-цифровой преобразователь (АЦП) 3, блок 4 сокращения избыточности, синхронизатор 5, ПЗУ 6 коэффициентов регрессионного сжатия по строкам, ПЗУ 7 коэффициентов регрессионного сжатия по столбцам, блок 8 формирования сжатых данных, блок 9 восстановления, сдвиговый регистра 10 и блок 11 формирования корректирующих данных.

Блок 4 сокращения избыточности (фиг. 2) содержит М + 1-разрядный регистр 10, М + 1 формирователей 14 группы коэффициентов правых частей нормальной системы и умножитель 15.

Формирователь 14 группы коэффициентов правых частей нормальной системы (фиг. 3) содержит умножитель 15, сумматор 16, М + 1-разрядный регистр 10 и четырехразрядный регистр 18.

ПЗУ коэффициентов регрессионного сжатия по строкам (фиг. 4) содержит счетчик 12 и М + 1 блоков 13 памяти.

Блок 8 формирования сжатых данных (фиг. 5) содержит четыре вычислителя 17 группы коэффициентов регрессионной модели.

Вычислитель группы коэффициентов регрессионной модели (фиг. 6) содержит три Р-разрядных регистра 10, накопитель 19 суммы попарных произведений и ПЗУ 20 коэффициентов обратной матрицы.

Накопитель 19 суммы попарных произведений (фиг. 7) содержит умножитель 15, сумматор 16, четырехразрядный регистр 18 и одноразрядный регистр 10.

Блок 9 восстановления (фиг. 8) содержит М + 4 М + 1-разрядных сдвиговых регистров 10 и М + 2 накопителей 19 суммы попарных произведений.

Блок 11 формирования корректирующих данных (фиг. 9) содержит сумматор 16, инвертор 23 и двухразрядный регистр 18.

Синхронизатор 5 (фиг. 10) содержит генератор 21 тактовых импульсов ТИ1, генератор 22 тактовых импульсов ТИ2, инвертор 23, делители 24-29 частоты по модулю 4, 4Р, Р + 1, n₂ + 1, (2М + 3) ˙ n₁, 2М + 3 соответственно, регистры 30, 31, 32, 33, 34, 35 с числом разрядов Р, Р, n₁, М + 1, М + 2, 2М + 3 соответственно.

Все входы и выходы элементов и узлов, используемых в системе для сжатия двумерного массива информации, изображенные на фигурах 1-10 и 12-14, имеют сквозную нумерацию с 1 по 247.

Система для сжатия двумерного массива информации работает следующим образом.

Аналоговые сигналы, представляющие функцию двух аргументов и получаемые путем сканирования в фиксированной прямоугольной области пространства аргументов, с выхода источника 1 информации поступают на вход дискретизатора 2, который производит выборку и запоминание мгновенных значений сигнала через фиксированные интервалы времени, обеспечивая тем самым представление двумерной информации в виде набора значений аналогового сигнала. АЦП 3 преобразует аналоговые сигналы, поступающие с выхода дискретизатора 2, в двоичный код. Таким образом, набор кодов на выходе АЦП представляет собой двумерный числовой массив инфоpмации, полученный путем разложения функции двух аргументов на фиксированное число элементов по n₂ строкам и n₁ столбцам. Элементы этого массива с выхода АЦП последовательно строка за строкой поступают на вход последовательных данных регистра 10 и на вход блока 4 сокращения избыточности. Основой для синхронизации работы всего устройства являются кадровый синхроимпульс (КСИ) и строчный синхроимпульс (ССИ), формируемые источником 1 информации и поступающие потребителям с первого и второго выходов источника соответственно. Импульс синхронизации момента формирования отдельного отсчета T_ij в пределах кадра формируется синхронизатором 5 и поступает на пятый вход дискретизатора 2 и восьмой вход АЦП.

Блок 4 сокращения избыточности (фиг. 2) формирует значения правых частей нормальной системы d_kl. На четырнадцатый вход блока 4 одновременно подаются коды, соответствующие значениям степеней первого фактора 1, X_1i, X_1i², X_1i^M. С такой же периодичностью на тринадцатый вход поступает значение T_ij, где i номер столбца; j номер строки. Умножитель 15 (фиг. 2) формирует значения T_ij, X_1iT_ij, X_1i^MT_ij, поступающие с частотой следования импульсов С3 на входы 72 формирователей 14 группы коэффициентов правых частей нормальной системы. На третий групповой вход блока 4 (фиг. 2, вход 15) поступают значения второго фактора 1, X_2j, X_2j², X_2j^M причем первое из этих значений поступает на вход 71 первого (верхнего на фиг. 2) формирователя 14, а последнее из значений на аналоговый вход (М + 1)-го формирователя.

Таким образом, на выходе умножителя 15 в схеме первого формирователя (фиг. 2) получается последовательность произведений 1.T_ij, X_1iT_ij, X_1i^MT_ij, поступающая с частотой управляющих импульсов серии СЗ (фиг. 12) на сумматор 16 (фиг. 3).

В (М + 1)-м формирователе 14 (фиг. 2) на выходе умножителя 15, входящем в его состав (фиг. 3), образуется последовательность произведений 1˙T_ij, X_1i˙T_ij˙X_2j, X_1i^MT_ijX_2j^M. После этого меняется значение i, т.е. на четырнадцатый вход блока 4 по- даются значения степеней первого фактора, соответствующих следующей в строке точке отсчета функции T_ij. При этом информация на пятнадцатом входе меняется только тогда, когда все значения T_ij в строке введены в блок 4. Это обеспечивается тем, что на вход 22 (25) ПЗУ 6 (7) подаются сигналы сброса счетчиков на "0" в моменты формирования строчного синхроимпульса ССИ (или сигнал конца кадрового синхроимпульса ККСИ), а на счетный вход 21 (24) счетчика 12 поступают импульсы серии С1, следующие синхронно с поступлением значений T_ij на ПЗУ 6, или ССИ, поступающие с частотой следования строк на ПЗУ 7.

Формирователь 14 (фиг. 3) работает следующим образом.

В регистре 10 формирователя хранятся значения S_j^kl, причем О ≅ k + l ≅ 2M, которые суммируются на каждом цикле серии импульсов С3, поступающей на вход 73, с ранее накопленной суммой Ski

^l (-n₂≅n≅ n₂).В конце ввода всего кадра всех значений T_ij в регистре 10 первого (верхнего на фиг. 2) формирователя 14 в разрядах с первого по (М + 1)-й оказывается М + 1 значение d_kl, где О ≅ k ≅ M, l 0, в разрядах регистра 10 второго формирователя 14 фиг. 2 с первого по М-й формируются М значений d_kl, где О ≅ k ≅ M 1, l 1. В регистре 10(М + 1)-го формирователя 14 на фиг. 2 (самого нижнего) в первом разряде формируется одно значение d_kl, где k 0, l М. Таким образом, в первом формирователе 14 формируется М + 1 значение, во втором М значений, в третьем М-1 значение и в (М + 1)-м одно значение, т.е. всего L значений коэффициентов d_kl.

Для синхронизации работы формирователей на вход 93 управления записью регистров 18 (фиг. 14) подаются импульсы серии С3, каждый импульс серии инициализирует одну операцию суммирования. При этом на вход 75 формирователей подаются импульсы сдвига по регистру 18 записанной в него единицы. На выходах разрядов регистра 18 (на фиг. 3) формируются сигналы синхронизации работы умножителя 15 (выход 78), синхронизации записи в регистры сумматора 16 (выход 79), сигнал записи результата суммирования в выходной регистр сумматора 16 (выход 80), сигнал сдвига информации в регистре 10 (выход 81). Начальный сброс регистра 10 и регистра 18 осуществляется подачей сигнала на вход 73 формирователей 14 в начале каждого кадра.

Блок 8 формирования сжатых данных (фиг. 5) вычисляет коэффициенты регрессионной модели b_kl, используя значения элементов правых частей d_kl, формируемых в блоке 4 сокращения избыточности, и коэффициентов обратной матрицы С^-1, которые хранятся в ПЗУ 20 (фиг. 6) коэффициентов обратной матрицы. При этом реализуются выражения (16), причем все четыре подвектора искомых коэффициентов регрессионной модели вычисляются одновременно в соответствии с формулами (17). Для однотипности вычислений матрицы (С⁰⁰)^-1, (С¹⁰)^-1, (С⁰¹)^-1, (С¹¹)^-1 берутся одинаковых размеров, определяемых наибольшим размером РmaxP^ij, i, j 0, 1, причем на места недостающих элементов в ПЗУ записаны нули. Подвекторы В⁰⁰, В¹⁰, В⁰¹, В¹¹ имеют размеры Р⁰⁰ Р₁, Р¹⁰ Р₂, Р01 Р₃, Р¹¹ Р₄.

Блок 8 имеет один групповой вход 27, по которому поступают значения d_kl, четыре входа 28, 29, 31, 33 синхронизации и один групповой выход 32, причем на групповой вход поступает L значений d_kl, а на групповом выходе получается L значений b_kl (четыре подвектора В^ij).

Рассмотрим работу первого (верхнего на фиг. 5) вычислителя 17 группы коэффициентов регрессионной модели (фиг. 6). Регистры 10 вычислителя Р-разрядные. С группового входа 108 вычислителя на ортогональные входы 129 регистра 10 поступает одновременно Р₁ значений d_kl в старшие разряды. Одновременно из ПЗУ 20 коэффициентов обратной матрицы параллельно передается вся строка обратной подматрицы (С⁰⁰)^-1 из Р чисел в регистр 10 (ортогональный вход 133). Значения подвектора D⁰⁰ и одной из строк матрицы (С⁰⁰)^-1 последовательно выводятся на входы 138 и 137 накопителя 19 суммы попарных произведений. При этом импульсы сдвига подаются на входы 130 и 132 синхронизации сдвига, а синхронизация записи чисел в регистре 10 из ПЗУ осуществляется подачей управляющего сигнала на вход 135. Подвектор D⁰⁰ при сдвиге регистра 10 одновременно записывается по входу 152 последовательных данных снова в регистр и находится в нем, пока не умножится последовательно на все строки подматрицы (С⁰⁰)^-1. В накопителе суммы попарных произведений (фиг. 7) умножитель 15 производит умножение элемента строки подматрицы (С⁰⁰)^-1 на элемент подвектора D⁰⁰, произведение поступает на вход 154 сумматора 16, на второй вход 155 которого поступает ранее накопленная сумма, и результат записывается в регистр 10 по входу 158. Под действием импульса сдвига регистра, подаваемого на вход 159, накопленная ранее сумма попарных произведений снова поступает на вход 155 сумматора 16. Таким образом, через Р циклов суммирования на выходе 142 формируется один элемент b_kl подвектора В⁰⁰ коэффициентов регрессионной модели. Это значение записывается по входу 145 в регистр 10 (фиг. 6). После Р повторений этой процедуры в регистре 10 на Р₁ ортогональных выходах 146 получается значение всего подвектора В⁰⁰. Аналогично формированию подвектора В⁰⁰ формируются подвекторы В⁰¹, В¹⁰ и В¹¹ на выходах 113, 119 и 125 (фиг. 5). Общее число коэффициентов, формируемых на выходе 32 блока 8, равно L Р₁ + Р₂ + Р₃ + Р₄.

В накопителе 19 (фиг. 7) четырехразрядный регистр 18 используется в качестве местного синхронизатора, аналогичного регистру 18 на фиг. 3. При этом в первый разряд сдвигового регистра записывается "1" подачей управляющего сигнала на вход 162, а импульсы сдвига подаются на вход 163 регистра 18 (фиг. 7).

Блок 9 восстановления (фиг. 8) работает следующим образом. На первый групповой вход 34 блока параллельно подаются L коэффициентов регрессионной модели b_kl (0 ≅ k + l ≅ M). При этом по регистрам 10 они распределены следующим образом. На ортогональные входы 168 верхнего регистра 10 подаются М + 1 коэффициентов b_kl (l_o0, 0 ≅ k ≅ M), на ортогональные входы второго регистра 10 подаются М коэффициентов b_kl, причем в самый младший разряд ничего не подается, т. е. туда записывается "0" (l 1, 0 ≅ k ≅ M 1). В последний (М + 1)-й регистр по групповому входу 34 поступает лишь один коэффициент b_kl (l M, k 0) в самый старший разряд, начиная с которого осуществляется вывод из регистра.

По синхроимпульсу серии С3 (вход 38 фиг. 8) осуществляется запись значений b_kl в (М + 1)-й регистр с группового входа и запись значений степеней первого фактора 1, X_1i, X_1i², X_1i^M по второму групповому входу 36 в (М + 2)-й регистр 10, а по строчному импульсу ССИ, поступающему по входу 40, с третьего группового входа 35 в (М + 3)-й регистр записываются значения степеней второго фактора 1, X_2j, X_2j², X_2j^M. На входы 176, 177 (фиг. 8) одновременно поступают значения b₀₀, b₁₀, b_M0 и 1, X_1i, X_1i², X_1i^M, а на выходе 181 накопителя 19 суммы попарных произведений получается сумма (М + 1)-го слагаемого регрессионной модели, записываемого в младший разряд (М + 4)-го регистра 10 по ортогональному входу 182. Другими словами, при М 3, например, формируется сумма b₀₀˙1 + b₁₀˙X_1i + b₂₀X_1i² + b₃₀˙X_1i³. На выходе второго сверху накопителя 19 (фиг. 8) получается сумма b₀₁˙1 + b₁₁˙X_1i + b₂₁X_1i². На выходе последнего сверху накопителя 19 получается b_0M˙1 и это значение последним выводится из (М + 4)-го регистра на вход 184 выходного накопителя 19, на вход 185 которого поступает из (М + 3)-го регистра 10 последовательность 1, X_2j, X_2j², _X2j^M. С выходов 183 и 194 синхронно поступают вышеуказанные накопленные суммы на входы 184 и 185, обеспечивая получение суммы произведений, аналогичных , , , указанным для М 3.

На выходе 189 образуются восстановленные по регрессионной модели значения , поступающие на блок 11 формирования корректирующих данных. Блок формирования корректирующих данных (фиг. 9) из значений и Т_ij, поступающих из сдвигового регистра 10 (фиг. 1) на вход 45, формирует разности T_ij, представляющие собой корректирующие данные. Эти данные, выводимые по второму выходу системы (выход 50 на фиг. 1), дополнительно к коэффициентам b_kl регрессионной модели, выводимым по выходу 30, позволяют точно восстановить исходные данные T_ij. Инвертор 23 на фиг. 9 служит для подготовки значения T_ij к вычитанию на сумматоре 16, причем знаковый разряд числа Т_ij поступает на отдельный вход 198 сумматора. Местный синхронизатор, выполненный на регистре 18, обеспечивает выдачу корректирующих данных синхронно с серией управляющих сигналов С1.

Синхронизация работы всей системы осуществляется блоком синхронизации (фиг. 10). Временная диаграмма представлена на фиг. 11-13. Основными сигналами управления системой являются кадровый синхроимпульс КСИ (вход 51) и строчный синхроимпульс ССИ (вход 52), а также сигналы ККСИ (конец кадрового синхроимпульса) и КК (конец кадра).

Особенностью синхронизации системы является наличие двух генераторов 21 и 22 тактовых импульсов ТИ1 и ТИ2, причем генератор ТИ1 обеспечивает формирование управляющих сигналов С1, С12, С3, С5, а генератор с другой тактовой частотой ТИ2 обеспечивает управляющие сигналы С4 и С7. Второй особенностью синхронизации работы системы является то, что период следования кадров информации содержит два участка: рабочую часть кадра, в течение которой производится передача информации от источника на вход дискретизатора (КСИ 0), и паузу (КСИ 1).

В течение рабочей части кадра формируются управляющие серии С1, С12, С3, С5, обеспечивающие формирование значений правых частей d_klнормальной системы, соответствующих (R + 1)-му кадру. Одновременно с вводом данных (R + 1)-го кадра формируются значения корректирующих данных R-го кадра, которые вместе с коэффициентами модели выводятся из системы. В течение паузы формируются значения коэффициентов b_klрегрессионной модели (R + +1)-го кадра на основании ранее вычисленных значений d_kl. Задержка от начала ввода данных в устройство до начала вывода коэффициентов модели и корректирующих данных равна периоду следования кадровых импульсов. Полностью все сжатые данные выведены спустя время, равное сумме длительности периода следования КСИ и длительности рабочей части кадра КСИ 0.

В синхронизаторе (фиг. 10) используются делители частоты 24 по модулю 4, 25 по модулю 4Р, 26 по модулю Р + 1, 27 по модулю n₂+1, 28 по модулю (2М+3) n₁ и 29 по модулю 2М + 3. Все делители имеют один вход сброса и один счетный вход. Делители могут быть выполнены по схеме фиг. 12 и представляют собой кольцевые регистры, в которые записывается одна "1" подачей сигнала на вход L, а импульсы счета подаются на вход синхронизации сдвига С. Регистры 30-35, формирующие необходимые управляющие последовательности (фиг. 15-17), построены на однотипных элементах и отличаются только числом разрядов и подключением ортогональных входов к уровню логической "1" или "0". Генераторы 22 и 23 синхронизируются по входам 208 и 206 кадровым синхроимпульсом. Синхронизатор формирует следующие серии сигналов (в скобках указаны выходы на фиг. 10): ТИ1 (58), ТИ2 (61), КК (59), ККСИ (62), С1 (56), С3 (53), С12 (60), С4 (54), С5 (55), С7 (57).

Система для сжатия двумерного массива информации относится к автоматике, телемеханике и вычислительной технике, в частности к обработке дистанционных (например, спутниковых) измерений. Целью изобретения является сокращение избыточности передаваемой информации, отображающей сложные немонотонные двумерные зависимости и содержащей случайную составляющую. Система содержит блок 8 формирования сжатых данных, блок 9 восстановления, сдвиговый регистр 10 и блок 11 формирования корректирующих данных, причем выходы блока 4 сокращения избыточности соединены с групповым входом блока 8 формирования сжатых данных. Введение в состав системы блока формирования сжатых данных, блока восстановления и блока формирования корректирующих данных позволяет до передачи данных произвести восстановление числового массива по сжатой информации, вычислить корректирующий массив разностей элементов исходного и восстановленного массива и передать не только массив сжатых данных, но и этот корректирующий массив разностей. Введение в блок сокращения избыточности М + 1-разрядного регистра, умножителя и М + 1 формирователей группы правых частей нормальной системы обеспечивает сжатие двумерных числовых массивов информации, отображающих сложные немонотонные зависимости, так как в блоке сокращения избыточности реализована регрессивная модель сжатия M-го порядка (M ≥ 2). 9 з. п. ф-лы, 1 табл. 18 ил.

1. СИСТЕМА ДЛЯ СЖАТИЯ ДВУХМЕРНОГО МАССИВА ИНФОРМАЦИИ, содержащая источник информации, дискретизатор, информационный вход которого соединен с информационным выходом источника информации, аналогоцифровой преобразователь, информационный вход которого соединен с выходом дискретизатора, выход соединен с первым входом блока сокращения избыточности, постоянное запоминающее устройство коэффициентов регрессионного сжатия по строкам, выходы которого соединены с первым групповым входом блока сокращения избыточности, постоянное запоминающее устройство коэффициентов регрессионного сжатия по столбцам, выходы которого соединен с вторым групповым входом блока сокращения избыточности, и синхронизатор, отличающаяся тем, что в нее введены блок формирования сжатых данных, имеющий с первого по четвертый входы, блок восстановления, имеющий первый, второй и третий групповые входы и с первого по шестой входы, сдвиговый регистр, блок формирования корректирующих данных, имеющий с первого по пятый входы, и блок сокращения избыточности, имеющий с первого по пятый входы, выходы блока сокращения избыточности соединены с групповым входом блока формирования сжатых данных, выходы блока формирования сжатых данных соединены с первым выходом системы и с первым групповым входом блока восстановления, второй групповой вход которого соединен с выходами постоянного запоминающего устройства коэффициентов регрессионного сжатия по строкам, третий групповой вход блока восстановления соединен с выходами постоянного запоминающего устройства коэффициентов регрессионного сжатия по столбцам, выход блока восстановления соединен с первым входом блока формирования корректирующих данных, второй вход которого соединен с выходом последовательных данных сдвигового регистра, вход последовательных данных которого соединен с выходом аналого-цифрового преобразователя, выход блока формирования корректирующих данных соединен с вторым выходом системы, первый выход источника информации соединен с первым входом синхронизатора, второй выход источника информации соединен с вторым входом синхронизатора, с первым входом постоянного запоминающего устройства коэффициентов регрессионного сжатия по столбцам, вторым входом постоянного запоминающего устройства коэффициентов регрессионного сжатия по строкам и четвертым входом блока восстановления, первый выход синхронизатора соединен с вторым входом блока сокращения избыточности и с вторым входом блока восстановления, второй выход синхронизатора соединен с первым входом блока формирования сжатых данных, третий выход синхронизатора соединен с первым входом блока восстановления, четвертый выход синхронизатора соединен со вторыми входами дискретизатора и аналого-цифрового преобразователя, со входом синхронизации сдвигового регистра, с пятым входом блока сокращения избыточности, с первым входом постоянного запоминающего устройства коэффициентов регрессионного сжатия по строкам и третьим входом блока формирования корректирующих данных, пятый выход синхронизатора соединен с четвертым входом блока формирования сжатых данных, шестой выход синхронизатора соединен с третьим входом блока сокращения избыточности, шестым входом блока восстановления и четвертым входом блока формирования корректирующих данных, седьмой выход синхронизатора соединен с вторым входом блока формирования сжатых данных, восьмой выход синхронизатора соединен с третьим входом блока восстановления и пятым входом блока формирования корректирующих данных, девятый выход синхронизатора соединен с третьим входом блока формирования сжатых данных, десятый выход синхронизатора соединен с четвертым входом блока сокращения избыточности, пятым входом блока восстановления, вторым входом постоянного запоминающего устройства коэффициентов регрессионного сжатия по столбцам. 2. Система по п.1, отличающаяся тем, что блок сокращения избыточности содержит M + 1 -разрядный регистр, умножитель и М+1 формирователь группы коэффициентов правых частей нормальной системы, причем, М+1 ортогональных входов регистра соединены с первым групповым входом блока, первый вход умножителя соединен с первым входом блока, второй вход умножителя соединен с выходом последовательных данных регистра, первый вход первого формирователя соединен с первым входом второго группового входа блока, М+1 выходов соединены с выходами блока, первый вход i-го формирователя соединен с i-м входом второго группового входа блока, М+2-i выходов i-го формирователя соединены с выходами блока, i=1,2, М+1, вторые входы формирователей соединены с выходом умножителя, третьи входы формирователей соединены с четвертым входом блока, вход синхронизации умножителя, вход синхронизации сдвига регистра, четвертые входы формирователей соединены с вторым входом блока, пятые входы формирователей соединены с третьим входом блока, вход синхронизации записи в регистр соединен с пятым входом блока. 3. Система по п.1, отличающаяся тем, что j-й формирователь группы коэффициентов правых частей нормальной системы (j=1,2 М+1) содержит умножитель, сумматор, М+1 разрядный регистр и 4-разрядный регистр, вход синхронизации записи данных которого является четвертым входом формирователя, вход синхронизации сдвига 4-разрядного регистра является пятым входом формирователя, входы сброса регистров являются третьим входом формирователя, первый выход ортогональных данных 4-разрядного регистра соединен с входом синхронизации умножителя, второй выход 4-разрядного регистра соединен с входом синхронизации записи входных данных сумматора, третий выход 4-разрядного регистра соединен с входом синхронизации записи результата в выходной регистр сумматора, четвертый выход 4-разрядного регистра соединен с входом синхронизации сдвига М+1-разрядного регистра, первый вход умножителя является первым входом формирователя, второй вход умножителя является вторым входом формирователя, выход умножителя соединен с первым входом сумматора, второй вход которого соединен с выходом последовательных данных М+1 разрядного регистра, выход сумматора соединен с входом последовательных данных М+1-разрядного регистра, ортогональные выходы которого с первого по М+2-j являются выходами формирователя. 4. Система по п.1, отличающаяся тем, что постоянное запоминающее устройство коэффициентов регрессионного сжатия по строкам и постоянное запоминающее устройство коэффициентов регрессионного сжатия по столбцам содержит М+1 блоков памяти коэффициентов регрессионного сжатия и счетчик, выход которого соединен с адресными входами блоков памяти коэффициентов регрессионного сжатия, счетный вход счетчика является первым входом постоянного запоминающего устройства, вход сброса счетчика является вторым входом постоянного запоминающего устройства, выходы блоков памяти коэффициентов регрессионного сжатия соединены с выходами постоянного запоминающего устройства. 5. Система по п.1, отличающаяся тем, что блок формирования сжатых данных содержит четыре вычислителя группы коэффициентов регрессионной модели, информационные входы К-го вычислителя являются K-й группой группового входа блока, первый, второй, третий, четвертый входы синхронизации вычислителей являются первым, вторым, третьим, четвертым входами блока формирования сжатых данных соответственно, выходы K-го вычислителя являются K-й группой выходов блока K=1,2,3,4. 6. Система по п.1, отличающаяся тем, что K-й вычислитель группы коэффициентов регрессионной модели содержит три p-разрядных сдвиговых регистра, постоянное запоминающее устройство коэффициентов обратной матрицы, накопитель суммы попарных произведений, ортогональные входы первого сдвигового регистра с 1-го по P_к-ый являются информационными входами вычислителя, K= 1,2,3,4, выход последовательных данных первого сдвигового регистра соединен с его входом последовательных данных и с первым входом накопителя суммы попарных произведений, выходы постоянного запоминающего устройства соединены с ортогональными входами второго регистра, выход последовательных данных которого соединен с вторым входом накопителя, выход накопителя соединен с входом последовательных данных третьего сдвигового регистра, ортогональные выходы с 1-го по P_к-ый третьего сдвигового регистра являются выходами вычислителя, вход синхронизации записи первого сдвигового регистра, второй вход постоянного запоминающего устройства коэффициентов обратной матрицы, четвертый вход накопителя суммы попарных произведений и вход сброса третьего сдвигового регистра являются четвертым входом синхронизации вычислителя, входы синхронизации сдвига первого и второго регистров и третий вход синхронизации накопителя суммы попарных произведений являются первым входом синхронизации вычислителя, входы синхронизации записи второго регистра, сдвига третьего регистра и первый вход постоянного запоминающего устройства являются вторым входом синхронизации вычислителя, пятый вход синхронизации накопителя является третьим входом синхронизации вычислителя. 7. Система по п.1, отличающаяся тем, что накопитель суммы попарных произведений содержит умножитель, сумматор, одноразрядный регистр и 4-разрядный регистр, первый вход умножителя является первым входом накопителя, второй вход умножителя является вторым входом накопителя, выход умножителя соединен с первым входом сумматора, выход сумматора соединен с входом последовательных данных одноразрядного регистра, выход которого соединен с вторым входом сумматора и является выходом накопителя, вход синхронизации записи 4-разрядного регистра является третьим входом накопителя, вход синхронизации сдвига 4-разрядного регистра является пятым входом накопителя, первый выход ортогональных данных 4-разрядного регистра соединен с входом синхронизации умножителя, второй и третий выходы 4-разрядного регистра соединены с входами синхронизации записи данных во входные регистры сумматора и записи результата в выходной регистр сумматора соответственно, четвертый выход 4-разрядного регистра соединен с входом синхронизации сдвига одноразрядного регистра, входы сброса регистров являются четвертым входом накопителя. 8. Система по п.1, отличающаяся тем, что блок восстановления содержит M+4 M+1-разрядных сдвиговых регистров и M+2 накопителя суммы попарных произведений, причем M+1-j ортогональных входов регистров с первого по M+1-й соединены с первым групповым входом блока, j=1,2, M+1, выходы последовательных данных регистров с первого по M+1-й соединены с их входами последовательных данных и с первыми входами накопителей суммы попарных произведений с первого по M+1-й, M+1 ортогональных входов M+2-го регистра являются третьим групповым входом блока, выход последовательных данных M+2-го сдвигового регистра соединен с вторыми входами накопителей суммы попарных произведений с первого по M+1-ый, M+1 ортогональный вход M+3-го регистра является вторым групповым входом блока, выход последовательных данных M+3-го регистра соединен с входом последовательных данных M+3-го регистра и с первым входом M+2-го накопителя суммы попарных произведений, выходы накопителей с 1-го по M+1-й соединены с ортогональными входами M+4-го сдвигового регистра, выход последовательных данных которого соединен с вторым входом M+2-го накопителя суммы попарных произведений, выход M+2-го накопителя является выходом блока, входы синхронизации записи с первого по M+1-ый регистр являются пятым входом блока, входы синхронизации сдвига с первого по M+2-й регистр, вход синхронизации записи M+4-го регистра и третьи входы синхронизации накопителей попарных произведений с первого по M+1-й являются вторым входом блока восстановления, вход синхронизации записи M+3-го регистра является четвертым входом блока, пятые входы синхронизации накопителей являются шестым входом блока, четвертые входы синхронизации всех накопителей и вход синхронизации записи M+2-го регистра являются третьим входом блока, входы синхронизации сдвига M+3-го и M+4-го регистров и третий вход синхронизации M+2-го накопителя являются первым входом блока. 9. Система по п.1, отличающаяся тем, что блок формирования корректирующих данных содержит сумматор, инвертор и двухразрядный регистр, первый вход сумматора является первым входом блока, второй вход сумматора является вторым входом блока, первый вход знака сумматора объединен в первым входом блока, второй вход знака сумматора соединен с выходом инвертора, вход которого является вторым входом блока, вход синхронизации записи во входные регистры сумматора соединен с первым выходом регистра, вход синхронизации записи результата в выходной регистр сумматора соединен с вторым выходом регистра, вход синхронизации записи регистра является третьим входом блока, вход синхронизации сдвига регистра является четвертым входом блока, вход сброса регистра является пятым входом блока, выход сумматора является выходом блока. 10. Система по п. 1, отличающаяся тем, что синхронизатор содержит два генератора тактовой частоты, инвертор, шесть делителей частоты по модулю 4, 4P, P+1, n₂+1, (2M+3) · n₁, 2M+3 соответственно и шесть регистров, содержащих P, P, n₁, M+1, M+2, 2M+3 разрядов соответственно, входы синхронизации первого и второго генераторов являются первым и вторым входами блока синхронизатора, вход инвертора, входы сброса второго и третьего делителей частоты и вход синхронизации записи первого регистра являются первым входом блока, входы сброса четвертого и пятого делителей частоты и вход синхронизации записи в третий регистр являются вторым входом блока, выход инвертора соединен со счетным входом четвертого делителя частоты, выход которого является седьмым выходом блока, выход первого генератора соединен со счетными входами пятого и шестого делителей частоты и является шестым выходом блока, выход пятого делителя соединен с входом синхронизации сдвига третьего регистра, выход которого соединен с входом сброса шестого делителя частоты, входами синхронизации записи четвертого, пятого и щестого регистров и является четвертым выходом блока, выход шестого делителя частоты соединен с входами синхронизации сдвига четвертого, пятого и шестого регистров, выходы которых являются первым, восьмым и третьим выходами блока соответственно, выход второго генератора соединен со счетными входами первого и второго делителей частоты и является девятым выходом блока, выход первого делителя соединен с входом синхронизации сдвига второго регистра, выход которого является вторым выходом блока, выход второго делителя частоты соединен с входом синхронизации сдвига первого регистра и со счетным входом третьего делителя, выход которого является десятым выходом блока, выход первого регистра соединен с входом сброса первого делителя частоты, входом синхронизации записи второго регистра и является пятым выходом блока.