Адаптивное устройство для сокращения избыточности цифровой информации

 

1. АДАПТИВНОЕ УСТРОЙСТВО ДЛЯ СОКРАЩЕНИЯ ИЗБЫТОЧНОСТИ ЦИФРОВОЙ ИНФОРМАЩ Ш, содержащее вычислитель разделенных разностей, первый выход которого соединен с входом вычислителя коэффициентов интерполяционного полинома,. выходы которого соединены с первыми входами формирователя 341ачений интерполяционного полинома, выход формирователя значений интерполяционного полинома соединен с первьм входом первого блока срайнения, ключ, первый выход которого соединен с входом блока памяти , выход которо го является выходом устройства, отличающееся тем, что. с целью повьшения быстродействия устройства, в него введены регистр адреса, элемент задержки, блок умножителей , второй блок сравнения и элемент И, первый вход регистра адреса и вход элемента задержки объединены и являются входом устройства, выход элемента задержки соединен с первым входом ключа, второй выход которого соединен с вторым входом регистра адреса и первым входом вычислителя разделенных разностей, выход блока умножителей соединен с третьим входом регистра адреса и вторым входом формирователя значений интерполяционного полинома, второй выход которого соединен с первым входом второго блока сравнения, первый, второй и третий выходы регистра адреса .соединены соответственно с объединенными входом блока умножителей и вторым входом вычислителя разделенных разностей , вторым входом первого и вторым входом второго блоков сравнения, выходы блоков сравнения соединены с соответствукмцими входами элемен- , та И, выход которого соединен с вторым входом ключа.

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

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

РЕСПУБЛИН

09) (11) 4(51) С 08 С 19/28

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

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

H ABTOPCHOMV СВИДЕТЕЛЬСТВ,К (21) 3648492/24-24 (22) 03.10.83 (46) 23.01.85. Бюл. М 3 (72) Г.И.Власов, Ф.Д.Межов и И.К.Окунева (53) 621.398(088.8) (56) 1; Авторское свидетельство СССР

N9 231350, кл. G 08 С 19/28, 1967.

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

В 725261, кл. Н 04 L 25/16, 1977 (прототип). (54)(57) 1. АДАПТИВНОЕ УСТРОЙСТВО

ДЛЯ СОКРАЩЕНИЯ ИЗБЫТОЧНОСТИ ЦИФРОВОЙ

ИНФОРМАЦИИ, содержащее вычислитель разделенных разностей, первый выход которого соединен с входом вычислителя коэффициентов интерполяционного полинома,,выходы которого соединены с первыми входами формирователя значений интерполяционного полинома, вь ход формирователя значений интерполяционного полинома соединен с первым входом первого блока сравнения, ключ, первый выход которого соединен с входом блока памяти, выход которо" го является выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью повьппения быстродействия устройства, в него введены регистр адреса, элемент задержки, блок умно жителей, второй блок сравнения и элемент И, первый вход регистра адреса и вход элемента задержки объединены и являются входом устройства, выход элемента задержки соединен с первым входом ключа, второй выход которого соединен с вторым входом регистра адреса и первым входом вычислителя разделенных разностей, выход блока умножителей соединен с третьим входом регистра адреса и вторым входом формирователя значений интерполяцион.

/ ного полинома, второй выход которого I соединен с первым входом второго блока сравнения, первый, второй и третий выходы регистра адреса соединены соответственно с объединенными входом блока умножителей и вторым Ф входом вычислителя разделенных разностей, вторым входом первого и вторым входом второго блоков сравнения, выходы блоков сравнения соединенй с соответствующими входами элемента И, выход которого соединен с вто-, рым входом ключа.

1136201

2 . Устройство по п . 1 ч а ю щ е е с я тем, что вычислитель разделенных разностей содержит элементы памяти, вычитатели и делитель, выходы первого элемента памяти соединены с первыми входами соответственно первого и второго вычитателей, выходы которых соединены соответственно с первым входом второго элемента памяти через делитель и с первым входом третьего элемента памяти, первый выход второго элемента памяти соединен с.вторым входом третьего элемента памяти, второй и третий входы соответственно второго и третьего элементов памяти и вход первого элемента памяти и вторые входы вычитателей и делителя являются соответственно первым и вторым входами вычислителя разделенных разностей, выходы второго и третьего элементов памяти являются выходом вычислителя разделенных разностей.

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

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

1

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

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

2 полинома, выход которого через блок . сравнения подключен к управляющему входу ключа выдачи данных; к сигналь.ному входу ключа выдачи данных и к .другому входу блока сравнения подключен выход блока выбора отсчетов входного сигнала, выход ключа соединен с выходным блоком (I $. Основным недостатком этого устрой,ства является его относительно неаы"оКое быстродействие„ так как в нем кроме интерполяции используется экстраполяция, сопровождаемая повыше3 1136201 4 нием степени полинома, следствием динен с входом вычислителя коэффичего является большой объем вычисле- циентов интерполяционного полинома ома» ний, которые должны .быть выполнены выходы которого соединены с первыми в единицу времени.

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

Ф второй и третий вых д

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

\ разностей, вторым входом первого и подключены к соответствующим вхо- вторым входом второго блоков сравнедам блока вычисления коэффициентов ния, выходы блоков сравнения интерполяционного полинома, выход соединены с соответствующими которого подключен к входу блока входами элемента И, выход когенерирования сигналов интерполя- торого соединен с вторым вхоционного полинома (21.

Недостатком известного устройства также является его невысокое

Кроме того, вычислитель разделен. быстродействие вследствие того, что 4О ных Разностей содержит элементы пасравнение ошибки интерполяции мяти, вычитатели и делитель, выходы с допустимой ошибкой необходимо де- пеРвого элемента памЯти соеДинены лать в каждой точке интервала ин- с пеРвыми вхоДами соответствеино терполяции, соответствующей непере-- пеРвого и втоРого вычитателей, выходанному отсчету. Поэтому объем необ- Ды котоРых соеДинены соответетвенно ходимых вычислений, приходящихся с пеРвым вхоДом втоРого элемента пана один интервал. между отсчетами мЯти чеРез Делитель и с первьаю вховходного сигнала (тактовый интервал), Дом тРетьего элемента памЯти, пеРвый возрастает пропорционально величине выхоД второго элемента памЯти сОеДиинтервала интерполяции.

50 нен с вторым входом третьего элемента памяти, второй и третий входы соответственно второго и третьего элебыстродействия ст ойст ментов .памяти и вход первого элемен- .

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

В качес"ве интерполяционного полинома используется кусочнополиномиальная функция третьей степени.

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

Формирователь значений интерполяционного полинома содержит умножители, преобразователи и сумматоры, выходы первого и второго преобразователей соединены с первыми входами 25 соответственно первого и второго умножителей, выходы которых соединены с первыми входами соответственно первого и второго сумматоров, выходы третьего и четвертого преобразователей соединены с первыми входами соответственно третьего и четвертого умножителей, выходы которых соединены с вторыми входами соответственно первого и второго сумматоров, 35 третьи входы которых соединены с выходами соответственно пятого и шестого умножителей, вторые входы первого, второго, третьего и четвертого умножителей, первые входы пятого и шестого умножителей, четвертые входы сумматоров являются .первыми входами формирователя зна- чений интерполяционного нолинома, объединенные входы преобразователей и вторые входы пятого и шестого умножителей и выходы сумматоров являются соответственно вторым вхо дом и первым и вторым выходами формирователя значений интерполяционного полинома; шага, что позволяет исключить блок хранения коэффициентов предыдущего шага и увеличить быстродействие уст" ройства.

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

Предлагаемое устройство (фиг.1) содержит вычислитель 1 разделенных разностей, вычислитель 2 коэффициентов интерполяционного полинома, формирователь 3 =-начений интерполяционного полинома, первый блок 4 сравнения, блок 5 памяти, ключ 6, блок 7 умножителей, элемент И 8, второй блок 9 сравнения, регистр 10 адреса, элемент 11 задержки. Вычислитель 1 разделенных разностей (фиг. 2} содержит вычитатели 12 и 13, элементы 14 — 16 памяти и делитель 17. Вычислитель 2 коэффициентов интерполяционного полинома содержит умножители 18 и 19, элементы 20 и 21 памяти и вычитатель 22.

Формирователь 3 значений интерполяционного полинома (фиг. 4) содержит. умножители 23-28, функциональные преобразователи 29-32 и сумматоры 33 и 34. Блок 5 памяти представляет собой запоминающий регистр. Блок 7 умножителей содержит два умножителя с общим входом. Один умножитель служит для умножения входной величины на 1/3, другой — для умножения входной величины на 2/3.

Регистр 10 адреса содержит К „+1 ячеек памяти с адресами О, 1,..., К „. Число К„„ „равно максимальной длине интервала интерполяции. Оно определяется либо свойствами сигнала, либо техническими воэможностями и экономическими соображениями. Например, для телевизионного сигнала вещательного стандарта К может быть пау равным числу отсчетов сигнала на одной телевизионной строке, т.е. в этом случае К „=600.

Принцип действия устройства заключается в том, что поступающие

113620 t с тактовой частотой отсчеты входного сигнала сравниваются по величине со значениями интерполяционного полино-. ма. Модуль разности между этими величинами является ошибкой интерполяции.

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

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

В качестве интерполяционного в предлагаемом устройстве использует- 15 ся полином третьей степени

S (б) =а +а„6+а Е +а 0 (1) где 9(= С/ ь — безразмерное время, измеряемое числом тактовых интервалов . 20

Коэффициенты а, а, а и а поли1 2 3 нома S(O) определяются с помощью опорных отсчетов следующим образом (фиг. 5): (2) z (1) 3 R

Пк-U где Dê= — —, к К 30

U0 и U — три последовательных опорных отсчета.

Вычисленные таким образом коэффициенты определяют полином (1) только на интервале интерполяции, ограниченном опорными отсчетами Uo u U . Ha фиг. 5 длина интервала интерполяции равна К, т.е. возможные значения аргумента 8 в формуле (1) определяются 4р выражением 0484К. Для определения очередного опорного отсчета интервал интерполяции последовательно, шаг за шагом увеличивается до тех пор, пока ошибка интерполяцйи не превысит допустимую величину. Как только это произойдет, отсчет U<4, бйвший отсчетом Пк на предыдущем шаге (фиг. 6a) делается опорным и процесс повторяется. На первом шаге

50 длина интервала интерполяции равна двум, на втором шаге — трем и т.д.

На К-1-м шаге длина интервала интерполяции равна К.

Рассмотрим .работу устройства на К-1-м шаге, который начинается в момент О=К (фиг. 6а), когда текущий отсчет входного сигнала поступает в регистр 10 адреса и записывает-i ся в адрес К (отсчет П1,). На преды- . дущем шаге в обоих блоках 4 и 9 срав. кения ошибка интерполяции не больше допустимой величины. В этом случае на выходе элемента И 8 появляется команда, по которой сигнальный выход ключа 6 запирается и отсчет Ut, (фиг. 6в), поступивший в этот момент на ключ 6 от элемента 11 задержки, не пройдет в блок 5. С другого выхода ключа 6 .подается команда,.по которой длина интервала интерполяции, равная до этого К-1, увеличивается на единицу и становится равной К, т.е. числа U и К из регистра 1О поступают в вычислитель 1 разделенных разностей соответственно на входы вычитателя 13 и делителя 17. Число К передается, кроме того, из вычислителя 1 в блок 7, где вычисляются целые числа дК=Б„-U, вычисляется в вычитателК ле 13 и Dк= — — в делителе 17.

Число D передается в блок 2 на вход вычитателя 22 и записывается в элементы 15 памяти, бывшее до этого в элементе 15 число D переносится в элемент 16 памяти. Выходы вычитателя t2 и элемента 16 памяти запираются.

В вычислителе 2 коэффициентов интерполяционного полинома произво1дятся следующие операции.

Число Вк из вычислителя 1 и коэффициент а из элемента 20 памяти поступает на входы вычитателя 22, на выходе которого получается число

Вк Пк"а 1

Число Вк подается на вход умножителя 18, где умножается на 2/К, в результате чего в соответствии с формулами (2) получается коэффициент а>, который подается на умножитель 19, где умножается на -1/2К, в результате чего получается коэффициент аз.

Полученные таким образом коэффициенты а и аз, а также хранящиеся в элементах 20 и 21 памяти коэффициенты а, ": а из вычислителя 2 о коэффици чтов передаются в формирователь 3 значений интерполяционйого полинома, где формируются два значения интерполяционного полинома (формула (1):

S

0 1 1 2 Ч

1136201 10 (2) ции превзойдет. допустимую, то с выхои

S> а,+а m +a>m +а m, соответствующие двум контрольным точ кам 9 m| и 6 =ш2. 5

Для получения S ÷èñëî m из блока 7 подается в формирователь 3 на общий вход умножителя 24 и функциональных преобразователей 29 и 30 °

Числа m и m с выходов преобразо- 1О вателей 29 и 30 подаются на входы умножителей 23 и 25. На другие входы умножителей 25, 23 и 24 из вычислителя 2 подаются коэффициенты полинома а, а и а,. С выходов умножите- 15 лей 25, 23 и 24 числа a>m, à m|

Э и а,ш„подаются на вход сумматора 34, куда подается также коэффициент а из вычислителя 2. На выходе сумматора 34 .получается, в соответствии 2о с формулой (3), число S ° Это число подается в блок 4 сравнения. Одновременно с числом S на выходе сумматора 33 аналогичным образом получается число Я, которое подается во 25 второй блок 9 сравнения.

Кроме формирователя 3 значений интерполяционного полинома числа m и ш2 одновременно подаются в блок 10 умножителей, где они служат командой,щ согласно которой отсчеты U(m ) и U(m>) из адресов.ш„ и m регистра 10 подаются соответственно в первый 4 и второй 9 блоки сравнения.

Модуль разности между значением полинома и отсчетом сигнала является ошибкой интерполяции. В первом блоке 4 сравнения вычисляется ошибка с =П„-U(m>) /, во втором блоке 9 сРавнения - ошибка с =/Si„-U(m 2)!. 40

Числа с и в блоках 4 и 9 сравниваются с допустимым значением ошибки d+ . Если У; cd+ (i =1,2), т.е. в обоих блоках 4 и 9 ошибка не превосходит допустимую, то от элемента И на ключ 6 подается команда, по которой вышеуказанный процесс повторяется, т.е. сигнальный выход ключа 6 запирается, интервал интерполяции увеличивается на единицу и т.д .

Если же хотя бы в одном из блоков 4 и 9 сравнения ошибка интерполяда элемента И поступит другая команда (фиг. 6а, б),по которой отсчет U<, переписывается в адрес "0", т.е.

Uo U<- отсчет U„ переписывается в адрес "1", т.е. U U„, а текущий отсчет U„+„ записывается в адрес "2", что означает U, U ; новое значение

Ь записывается в элемент 14 памяти в вычислителе 1; число 0< иэ элемента 16 памяти в качестве нового значе ния а„ передается в элемент 20 памяти вычислителя 2; разность D„=U„-Па с выхода вычитателя 12 записывается в элемент 16 памяти в вычислителе 1;

U -U разделенная разность D =- — выУ численная с помощью вычитателя 13 и делителя 17 (блок 1), записывается в элемент 15 памяти и передается в вычислитель 2 для вычисления коэффициентов а и а . Дальше устройство работает точно так же, как и на К-1-м шаге, только теперь К=2, т.е. первый шаг.

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

Поскольку в предлагаемом устройстве оценка ошибки осуществляется параллельно в двух блоках сравнения, то фактически на эту операцию затрачивается столько времени, как еслй бы контрольная точка была одна. Поэтому число операций, которые нужно выполнить за один тактовый интервал в предлагаемом устройстве, в N=K /2 раз меньше, чем в известном. На йрактике всегда N) 10.

11362О1

1136201

1136201

Йи к

Ц(4ф д 1 2 ° ° ° g-1 l(ill+1

0 1 2

0 2 ° ° °

Фиаб

К К+1

Заказ 10289/39 Тираж 611 Подписное

ВНИИПИ Государственного комитеть СССР по делам изобретений и открытий 113035, Иосква, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", г.ужгород, ул.Проектная, 4

Составитель Н.Бочарова

Редактор А.Козориз Техред Л.Коцвбняк Корректор:С.Шекмар