Устройство для сжатия двумерных массивов информации

 

Изобретение относится к автоматике и вычислительной технике ,в частности, к устройствам данных дистанционных измерений, получаемых, например, с помощью метеорологических спутников Земли. Цель изобретения - сокращение избыточности передаваемой информации. Для достижения указанной цели в устройство, содержащее синхронизатор 5 и блок 4 сокращения избыточности по строкам и столбцам, введены формирователи 7 и 8 коэффициентов регрессионного сжатия по строкам и столбцам соответственно, а также соответствующие связи. 3 з.п. ф-лы, 4 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„SU„„1497620

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

n+) х.= б 2

m+) х . г) 2

4 2 ) с- 2 х . = х — --- х

m, 2/

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4289042/24-24 (22) 22.07.87 (46) 30.07.89. Бюл. Р 28 (71) Ленинградский политехнический институт им. M.È.Êàëèíèíà (72) В.С.Тарасов, В.С.Тутыгин и В.И.Филимонов (53) 681.3 (088.8) (56) Авторское снидетельство СССР

)) - 125604), кл. G 06 F 15/20, 1985.

Авторское свидетельство СССР

)) 485489, кл. G 08 С )9/28, )974. (54) УСТРОЙСТВО ЛЛЯ СЖАТИЯ ДВУМЕРН)1Х

МАССИВОВ ИНФОРМАЦИИ (57) Изобретение относится к автомаИзобретение относится к автоматике и вычислительной технике, в частности к обработке данных дистанционных измерений, получаемых, например, с помощью метеорологических спутников Земли.

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

Рассмотрим сжатие двумерного массива информации, содержащего N =

= n x m чисел (точек ), где n — число точек в строке массива; m — - число точек в столбце массина. Начало координат — в центре массива.

В качестве основных коэффициентов регрессионного сжатия используются величины х,; и х, вычисляемые по формулам: (51) 4 G 06 F 15/20, G 08 С 19/28 тике и вычислительной технике, н част ности к устройствам обработки

1 данных дистанционных измерений, получаемых, например, с помощью метеорологических спутникон Земли. Цель изобретения — сокращение избыточности передаваемой информации. Лля достижения указанной цели в устройство, содержащее синхронизатор 5 и блок 4 сокращения избыточности по строкам и столбцам, введены формирователи 7 и 8 коэффициентов регрессионного сжатия по строкам и столбцам соответственно, а также со- ответствующие связи. 3 з.п. A-лы, 4 ил. представляющие собой безразмерные координаты по строке и столбцу массива данных.

В качестве дополнительных коэффициентов используют я величины х + и

1i вычисляемые пп формулам:

2J и х". = х . — --- > х

1 1 п 1

1 ° 1

Приведенные наборы значений х,, i = 1 ...,п; х, ) = 1,.. ° Äm рассматриваются как компоненты основных наборов коэффициентов регрессионного

3 1497 сжатия по строке и столбцу соответственно а х . и х — как компо» 1i 2j ненты дополнительных наборов коэффициентов по строке и столбцу соответственно.

620

T(x»x ) = bI»+ Ь, х„+ Ь2х2+

Входные данные поступают последовательно слева направо строчка эа строчкой.

Частичные суммы .вычисляются по формулам: и

S, -y т,.;

1 1 л

Б2 4 Х2 ° т»1 Х 2 »

1 j ., j Ij л

S » х+. Т"= х+ . S

21 1) 2! 1j и

1С е и (х* )

1С

C-=1 г

C-1 2C и 20

Х2 TIj Х2 1 Х!. т!1

j 1, ) г т;

Частичные суммы накапливаются и

I после поступления всех чисел массива формируются выходные величины:

Я5

Ь г

Я ь

2l

S4

Ш!

1 z

1С

52

b ю

S1

S1., S+

1! Ф

Я; Я 5

1%I . °

b

11

J Ъ !

Ih представляющие собой сжатый образ исходного двумерного массива данньж .

Исходные данные в двумерном массиве представлены с помощью К, десятичньж разрядов цифр. Величины S

» °

S представляются с помощью К 2 деС сятичных разрядов, определяемых из соотношения

К 2=

Коэффициент сжатия определяется из формулы

И.К! м к

К с,к где М вЂ” число передаваемых данных

В линию свя.IH, Коэффициент сжатия пропорционален числу точек 11 исходного массива и линейно возрастает с увеличением размеров фрагмента N = п m.

S х

h S - = P х,.

5) л

ЯС = 2х„.

laI

Для восстановления информации по сжатым данным используется известное уравнение регрессии

+Ьх+bх+Ьх1х

2 2

22 2 12 определяющее поверхность наилучшего приближения, Перед вычислением коэффициентов регрессии Ь; определяют вспомогательные величины, которые остаются постоянными для массива заданных размеров: и ге2» (х хсе) е

Коэффициенты регрессии находятся из соотношений:

»! 9!

Я! b11 ч- 2 Ь22

ba х х

N N е., 1е N С-, 2е

Задавая значения х 1 и х <, можно определить восстановленное значение температуры Т,. в любой строке или

11 столбце двумерного массива.

Дисперсия воспроизводимости рассматриваемого исходного массива и

1 л 2

S = --- (Т вЂ” Т ) т ь1 1 - е е е.

Среднеквадратическое отклонение (СКО).

На фиг.1 изображена блок-схема устройства для сжатия двумерных массивов информации; на фиг.2 — схема блока сокращения избыточности; на фиг.3— схема блока формирования элемеНтов выходного массива; на фиг.4 — схема

5 14 формирователя коэффициентс в регресси онного сжатия.

Устройстно для сжатия двумерных массивов информации (фиг.1) нключает источник 1 информации, дискретизатор 2, аналого-цифровой преобразователь 3, блок 4 сокращения избыточности по строкам и столбцам, синхронизатор 5, блок 6 памяти, формирователь

7 коэффициентов регрессионного сжатия по строкам и формирователь 8 коэффициентов регрессионного сжатия по столбцам.

Блок 4 сокращения избыточности по строкам и столбцам (фиг,2) содвржит шесть одинаковых блоков 9 формирования элементов выходного массива.

Блок 9 формирования элементов выходного массива содержит умножители

10 и 11 и накапливающие сумматоры 12 и 13.

Формирователи 7 и 8 коэффициентов регрессионного сжатия по строкам и столбцам соответственно (фиг.4) содержат адресный счетчик 14 по модулю и и m соответственно и три блока

15 памяти.

Устройство для сжатия двумерных массивов информации (фиг.4 и 1) работает следующим образом.

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

2, н двоичный код. Таким образом, набор кодов на выходе аналого-цифрового преобразователя представляет собой двумерный числовой массив информации, полученный путем разложения функции двух аргументон на фиксированное число элементов по т строкам и и столбцам.

Массив m к п кодов с выхода аналого-цифрового преобразователя посту-, пает на вход блока 4 сокращения избыточности по строкам и столбцам. На

97(120

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

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

20 и единичный наборы по строкам содержат п числовых констант каждый, причем компоненты основного набора вычисляются как i — и+1)/2, где номер компоненты, 1 = 1,2,...п

25 компонента дополнительного набора определяется как разность квадрата соответствующий компоненты основного набора и суммы квадратов значений всех компонент основного набора, по3р деленной на и, компонента единичного набора равна единице. Основной, дополнительный и единичный наборы по столбцам содержат m числовых констант каждый, причем компоненты основного набора вычисляются как †(m+1)/2, где j — номер компоненты, ) = 1,2,...m; )-я компонента дополнительного набора определяется как разность квадрата соответствую4р щей компоненты основного набора и суммы квадратов значений всех компонент основного набора, поделенной на m, компонента единичного набора равна единице.

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

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

Блок 4 сокращения избыточности обеспечинает преобри онание m n

1497620 компонент входного двумерного массива, п компонент основного набора по .строкам, и компонент дополнительного наоора по строкам, п компонент единичного набора по строкам, ш компонент основного набора по столбцам, m компонент дополнительного набора по столбцам, m компонент единичного набора по столбцам в шесть 1ð числовых элементов выходного массива, используя которые, можно восстановить исходный массив m n элементов .

Точность восстановления исходного массива будет зависеть от размерности 15 массива и информационных характеристик сжимаемого сигнала. Значения компонент по строкам и столбцам определяются только размерностью массива исходных данных и не зависят от значе- 20 чий измеряемого сигнала.

Элементы-выходного массива с выходов блока 4 сокращения избыточности поступают на вход блока 6 памяти. 25

Блок 6 памяти принимает шесть числовых элементов выходного массива от блока 4 сокращения избыточности после поступления всех m п элементов исходного массива. Элементы исходно- 30 го массива могут представлять фрагмент ипи подмассив более обширного двумерного поля данных. В этом случае оперативное запоминающее устройство выполняет функцию буферного запоминающего устройства, осуществляющего временное хранение передаваемой информации, необходимого для органиэации равномерной во времени последовательной передачи элементов выход- 40 ного массива.

Блок 4 сокращения избыточности по строкам и столбцам работает следующим образом (фиг.2).

Элементы входного массива Т;1, где 45

1 — номер столбца,j — номер строки, поступают последовательно с выхода аналого-цифрового преобразователя на вход (1). На входы (2), (3) и (4) поступают с часто- 51 той следования элементов входного массива в строке компоненты основного, дополнительного и единичного наборов коэффициентов регрессионного сжатия по строкам, причем каждому элементу строки массива соответствует определенная компонента каждого набора. На входи (5),(6) и (7) поступают с частотой следования строк входного массива компоненты основного, дополнительного и единичного наборов коэффициентов регрессионного сжатия по столбцам, причем каждой строке массива соответствует определенная компонента каждого набора. На выходах (8) †(13) к моменту окончания поступления элементов входного массива T" формируются значения шести элементов выходного массива, представляющие сжатый образ исходной информации.

Блок 9 формирования элемента входного массива работает следующим образом (фиг.3).

На вход (14) умножителя 10 поступают последовательно элементы входного массива Т;, на вход (15) умножителя 10 и на вход (16) умножителя 11 — последовательно компоненты наборов коэффициентов регрессионного сжатия по строкам и столбцам. Умножитель 10 выполняет умножение элементов массива Т 1 и компонент наборов коэффициентов регрессионного сжатия, поступающих на вход (15), в моменты времени, соответствующие дискретности поступления элементов в строках массива Т,1 . Сумматор 12 выполняет суммирование чисел, поступающих с выхода умножителя 10, и накопление частичных сумм S ! У

1,2,...,m, произведений, соответствующих строкам массива Т . Умноty житель 11 выполняет умножение значений частичных сумм произведений S ф поступающих с частотой следования строк массива Т с выхода накапли1) вающего сумматора 12, на значения компонент соответствующего набора коэффициентов регрессионного сжатия,, поступающих на вход (16) блока 9 формирования элементов выходного массива.

Умножение в умножителе !1 производится с частотой поступления значений частичных сумм произведений по строкам S I или с частотой поступления строк массива Т,1 . Накапливающий сумматор 13 выполняет суммирование чисел, поступающих с выхода умножителя 11, и накопление итоговой суммы произведений.

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

1497б20

Ф о р м у л а и з о 6 р е т е н и я

1. Устройство для сжатия двумерных массивов инАормации, содержащее блок сокращения избыточности по стро5 кам и столбцам и синхронизатор, управляющий выход которого соединен с синхровыходом устройства, информационный вход которого соединен с первым информационным входом блока сокращения избыточности по строкам и столбцам, о т л и ч а ю щ е е с я тем, что, с целью сокращения избыточности передаваемой информации, в него введены Аормирователи коэАфици- 15 ентов регрессионного сжатия по строкам и столбцам, первый, второй и третий выходы которых соединены соответственно с вторым, третьим, четвертым и пятым, шестым, седьмым инфор- 2О мационными входами блока сокращения избыточности по строкам и столбцам, с первого по шестой инАормационные выходы которого соединены соответственно с первого по шестой информаци- 25 онными выходами устройства, первый и второй счетные. выходы синхронизатора соединены со счетными входами формирователей коэАфициентов регрессионного сжатия соответственно по строкам 30 и столбпам.

2. Устройство по п.1, о т л и ч а ю щ е е с я, тем, что Аормирователь коэААициентов регрессионного сжатия содержит блоки памяти основно- З5 го, дополнительного и единичного наборов коэффициентов регрессии соответственно и счетчик, выход которого соединен с адресными входами блоков памяти основного, дополни- 4р тельного и единичного наборов коэффициентов регрессии, выходы которых соединены соответственно с первым, вторым и третьим информационными выходами Аормирователя, счетный вход 4 которого соединен со счетным входом счетчика.

3. Устройство по п.1, о т л ич а ю щ е е с я тем, что блок сокращения избыточности содержит шесть формирователей элементов выходного массива, выходы которых соединены соответственно с, первого по шестой информационными выходами блока, Ilpp ный информационный вход которого соединен с первыми информационными входами с первого по шестой формирователей элементов выходного массива, второй информационный вход блока соединен с вторым информационным входом четвертого формирователя элементов выходного массива, третий информационный вход блока соединен с вторыми инАормационными входами второго и третьего формирователей элементов выходного массива, четвертый информационный вход блока соединен с вторым инАормационным входом первого формирователя элементов выходного массива, пятый информационный вход блока соединен с третьим инАормационным входом третьего формирователя элементов выходного массива и вторым информационным входом пятого Аормирователя элементов выходного массива, шестой инАормационный вход блока соединен с вторым информационным входом шестого Аормирователя элементов выходного массива, седьмой информационный вход блока соединен с третьими информационными входами первого, второго, четвертого, пятого и шестого Аормирователей элементов выходного массива.

4. Устройство по п.З, о т л и ч а ю щ е е с я тем, что формирователь. элементов выходного массива содержит два умножителя и два накапливающих сумматора, выход произведения первого умножителя соединен с входом первого накапливающего сумматора, выход которого соединен с входом первого множимого второго умножителя, выход произведения которого соединен с входом второго накапливающего сумматора, выход которого соединен с инАормационным выхо"< дом формирователя, первый информационный вход которого соединен с входом первого множимого первого умножителя, вход второго множимого которого соединен с вторым инАормационным входом формирователя, третий инАормационный вход которого соединен с входом второго мнонимого второго умножителя.

1 191620

gus.1

Составитель А.Богословских

Редактор А.Лежнина Техред М.Ходанич Корректор T.Êîëá

Заказ 4445/49 Тираж 668 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101