Адаптивное устройство для сокращения избыточности цифровой информации Советский патент 1985 года по МПК G08C19/28 

1136

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

3. Устройство по п. 1, о т л и,члющееся тем, что вычислитель коэффициентов интерполяционного полинома содержит элементы памяти, умножители и вычитатель, первый выход первого элемента памяти соедине с первым входом вычитателя, выход которого соединен с первым входом первого умножителя, выход которого соединен с первым входом второго умножителя, входы первого и второго элементов памяти и вторые входы вычитателя и умножителей являются входом вычислителя коэ|})фициентов интерполяционного полинома, выходы умножителей и второго элемента памяти и второй выход первого элемента памяти являются выходами вычислителя коэффициентов интерполятдионного. полинома. 4. Устройство по п. 1, о т л иЧаю|цееся тем, что формирователь значений интерполяционного полинома содержит умножители, преобразователи и сумматоры, выходы первого и второго преобразователей соединены с первыми входами соответственно первого и второго умнолсителей, выходы которых соединены с первыми входами соответственно первого и второго сумматоров, выходы третьего и четвертого преобразователей соединены с первыми входами соответственно третьего и четвертого умножителей, выходы которых соединены с вторьми входами соответственно первого и второго cyw маторов, третьи входы которых соединены с выходами соответственно пятого и шестого умножителей, вторые входы первого, второго, третьего и четвертого умножителей, первые входы пятого и шестого ьмножителей, четвертые входы сумматоров являются первыми входами формирователя значений интерполяционного полинома, объединенные входы преобразователей и вторые входы пятого и шестого умножителей и выходы cyMiviaTOpoB являются соответственно вторым входом и первым и вторым ВЬЕ одами формиро - вателя значений интерполяционного полинома.

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

Изобретение относится к промышленности средств связи и может быть использовано, например, в цифровых телевизионных передающих системах для построения устройств сокращения избыточности цифровой информации. Известно устройство для сокращения избыточности цифровой информаци содержащее блок выбора отсчетов входного сигнала, выход которого подключен к входу блока вычисления разделенных разностей, блок генерирования сигналов интерполяционного п олинома, выход которого через блок сравнения подключен к управляющему входу -ключа выдачи данных; к сигнальному входу ключа вьщачи данных и к другому входу блока сравнения подключен выход блока выбора отсчетов входного сигнала, вьпсод ключа соединен с выходным блоком Cl} Основным недостатком этого устройства является его относительно н.ёаысокое быстродействие,, так как в нем кроме интерполяции используется экстраполяция, сопровождаемая повышекием степени полинома, следствием чего является большой объем вычисле ний, которые должныбыть выполнены в единицу времени. Наиболее близким к изобретению по технической сущности является ус ройство, содержащее блок хранения отсчетов входного сигнала, выход ко торого подключен к входу блока вычи ления разделенных разностей, блок г нерирования сигналов интерполяционного полинома, выход которого через блок сравнения подключен к управляю щему входу ключа вьщачи данных, сиг нальный вход ключа выдачи данных и другой вход блока сравнения подкл чен к выходу блока хранения отсчетов входного сигнала, выход ключа выдачи данных подключен к выходному блоку. Кроме того, устройство содер жит блок разрешения вычислений и последовательно соединенные блок вы числения коэффициентов интерполяцио ного полинома и блок хранения коэффициентов предыдущего шага, к управ ляющему входу которого через блок разрешения вычислений подключен дополнительный выход блока сравнения, выходы блока храйения коэффициентов :предьщуще о шага, блока хранения )отсчетов входного сигнала и блока вычисления разделенных разностей подключены к соответствующим входам блока вычисления коэффициентов интерполяционного полинома, вьпсод которого подключен к входу блока генерирования сигналов интерполяционного полинома 1,2, Недостатком известного устройства также является его невысокое быстродействие вследствие того, что сравнение ошибки интерполяции с допустимой ошибкой необходимо делать в каждой точке интервала интерполяции, соответствукодей непереданному отсчету. Поэтому объем необ ходимых вычислений, приходящихся на один интервал между отсчетами входного сигнала (тактовый интервал возрастает пропорционально величине интервала интерполяции. Цель изобретения - повьшение быстродействия устройства. Цель достигается тем, что адаптивное устройство для сокращения .избыточности цифровой информации, содержащее вычислитель разделенных разностей, первый выход которого сое динен с входом вычислителя коэффициентов интерполяционного полинома, выходы которого соединены с первыми входами формирователя значений интерполяционного полинома, выход формирователя значений интерполяционного полинома соединен с первым входом первого блока сравнения, ключ, первый выход которого соединен, с входом блока памяти, выход которого является выходом устройства, введены регистр адреса, элемент задержки, блок умножителей, второй блок сравнения и элемент И, первый вход регистра адреса и вход элемента задержки объединены и являются входом устройства, вьгход элемента задержки соединен с первым входом ключа, второй выход которого соединен с вторым входом регистра адреса и первым входом вычислителя разделенных разностей, выход блока умножителей соединен с третьим входом регистра адреса и вторым входом формирователя значений интерполяционного полинома, второй выход которого соедииен с первым входом второго блока сравнения, первый, второй и третий выходы регистра адреса соединены соответственно с объединенными входом блока умножителей и вторым входом вычислителя разделенных разностей, вторым входом первого и вторым входом второго блоков сравнения, выходы блоков сравнения соединены с соответствующими входами элемента И, выход которого соединен с вторым входом ключа.. . . Кроме того, вычислитель разделённых разностей содержит элементы памяти , вычитатели и делитель, выходы первого элемента: памяти соединены с первыми входами соответственно первого и второго вычитателей, выходы которых соединены соответственно с первым входом второго элемента памяти через делитель и с первьн входом третьего элемента памяти, первый выход второго элемента памяти соединен с вторым входом третьего элемента памяти, второй и третий входы соответственно второго и третьего элементов .памяти и вход первого элемента памяти и вторые входы вычитателей и делителя являются соответственно ервым и вторьм входами вычислителя азделенных разностей, выходы второго и третьего элементов памяти являются выходом вычислителя разделенных разностей. Вычислитель коэффициентов интерполяционного полинома содержит элементы памяти, умножители и вычитатель, первый выход первого элемента памяти соединен с первым входом вычитателя, выход которого соединен с первым входом первого умножителя, выход которого соединен с первым входом второго умножителя, входы пер вого и второго элементов памяти и вторые входы вычитателя и умножителей являются входом вычислителя коэф фициентов интерполяционного полинома, выходы умножителей и второго элемента памяти и второй выход первого элемента памяти являются выхода ми вычислителя коэффициентов интерполяционного полинома о Формирователь значений интерполяционного полинома содержит умножители преобразователи и сумматоры выходы первого и второго преобразователей соединены с первыми входами соответственно первого и второго умножителей, выходы которых соедине ны с первыми входами соответственно первого и второго сумматоров, выход третьего и четвертого преобразовате лей соединены с йервыми входами соо ветственно третьего и четвертого умножителей, выходы которых соединены с вторыми входами соответствен но первого и второго сумматоров, третьи входы которых соединены с выходами соответственно пятого и шестого з;т ножителеЙ5 вторые входы первого, второго, третьего и четвертого умножителей, первые входы пятого и шестого умнозкителей, четвертые входы сумматоров являются .первыми входами формирователя значений интерполяционного полинома, объединенные входы преобразователей и вторые входы пятого и шестого умножителей и выходы сумматоров являются соответственно вторым входом и первым и вторым выходами формирователя значений интерполяционного полинома. В качестве интерполяционного пол нома исполг зуется кусочнополиномиальная функция третьей степени. В отличие от известного устройства коэффициенты этой функции, вычисляе мые на интервале интерполяции, не зависят от коэффициентов предыдущег шага, что позвол1 ет исключить блок хранения коэффициентов предыдущего шага и увеличить быстродействие устройства. На фиг. 1 показана структурная схема предлагаемого устройства; на фиг. 2 - структурная схема вычислителя разделенных разностей; на фиг. 3 - структурная схема вычислителя коэффициентов интерполяционного полинома; на фиг. 4 - структурная схема формирователя значений интерполяционного полинома; на фиг. 5 и 6 - графики, поясняющие принцип действия предлагаемого устройства. Предлагаемое устройство (фиг.1) содержит вычислитель 1 разделенных разностей, вычислитель 2 коэффициентов интерполяционного полинома, формирователь 3 значений интерполяционного полинома, первый блок А сравнения, блок 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 адреса содержит ячеек памяти с адресами 0,1,..., K j paBHo максимальной длине интервала интерполяции. Оно определяется либо свойствами сигнала, либо техническими возможностями и экономическими соображениями. Например, для телевизионного сигнала может быть щательного стандарта равным числу отсчетов сигнала на одной телевизионной строке, т.е. в этом случае . Принцип действия устройства заключается в том, что поступающие 7113 с тактовой частотой отсчеты входного сигнала сравниваются по величине со значениями интерполяционного полино-ма. Модуль разности между этими величинами является ошибкой интерполяции На выход устройства пропускаются лишь те опорные или существенные отсчеты, по которьм на приемной стороне могут быть вычислены значения интерполяционного полинома, используемые вместо непереданных отсчетов, причем ошибка интерполяции не превзойдет допустимой величины. В качестве интерполяционного в предлагаемом устройстве используется полином третьей степени 8{0)ао+а е+а2в2+аз0 (1) где 6( t/T - безразмерное время, измеряемое числом тактовых интервалов f. Коэффициенты а, а, а и а полинома 3(0) определяются с помощью опорных отсчетов следующим образом (фиг. 5): Uciy,:. я П 0 o а --2 (); 3 2К D . к к и,. и„ и и три последователь ных опорных отсче та. Вычисленные таким образом коэффи циенты определяют полином (1) тольк на интервале интерполяции, ограниче ном опорными отсчетами Ug и U. На фиг. 5 длина интервала интерполяции равна К, т.е. возможные значения ар гумента 6 в формуле (1) определяютс выражением . Для определения очередного опорного отсчета интерва интерполяции последовательно, шаг за шагом увеличивается до тех пор, пока ошибка интерполяции не превыси допустимую величину. Как только это произойдет, отсчет U. , бьшший отсчетом Uj, на предыдущем шаге (фиг. 6а), делается опорным и процесс повторяется. На первом шаге длина интервала интерполягщи равна двум, на втором шаге - трем и т.д. На К-1-м шаге длина интервала интер поляции равна К. Рассмотрим .работу устройства на К-1-м шаге, который начинается в момент (фиг. 6а), когда текущий отсчет входного сигнала поступа ет в регистр 10 адреса и записывает-i ся в адрес К (отсчет U,) . На предыдущем шаге в обоих блоках 4 и 9 сравнения ошибка интерполяции не больше допустимой величины. В этом случае на выходе элемента И 8 появляется команда, по которой сигнальный выход ключа 6 запирается и отсчет U ц.2 (фиг. 6в), поступивший в этот момент jHa ключ 6 от элемента 11 задержки, не пройдет в блок 5. С другого выхода ключа 6 подается команда, по которой длина интервала интерполяции, равная до этого К-1, увеличивается на единицу и становится равной К, т.е. числа U и К из регистра 10 поступают в вычислитель 1 разделенных разностей соответственно на входы вычитателя 13 и делителя 17. Число К передается, кроме того, из вычислителя 1 в блок 7, где вычисляются целые числа ГК Г2Кil3j 2 rjdK-U| -U. вычисляется в вычитате13 и в делителе 17. Число П. передается в блок 2 на вход вычитателя 22 и записывается в элементы 15 памяти, бывшее до этого в элементе 15 число Пц переносит ся в элемент 16 памяти. Выходы вычитателя 12 и элемента 16 памяти запираются. В вычислителе 2 коэффициентов интерполяционного полинома произвоДЯТСЯ следующие операции. Число В ИЗ вычислителя Т и коэффициент а из элемента 20 памяти поступает на входы вычитателя 22, на выходе которого получается число Число В подается на вход умножителя 18, где умножается на 2/К, в результате чего в соответствии с формулами (2) получается коэффициент а, который подается на умножитель 19, где умножается на -1/2К, в результате чего получается коэффициент ад. Полученные таким образом коэффициенты aj и aj, а также хранящиеся в элементах 20 и 21 памяти коэффициенты а, -: а из вычислителя 2 коэффици нтов передаются в формирователь 3 значений интерполяционного полинома, где формируются два значения интерполяционного полинома (формула (1):

(2)

S,,jm,2+ajm,и

, соответствутор ие двум контрольным точкам e«mj, и .

Для получения S число т из блока 7 подается в формирователь 3 на общий вход умножителя 24 и функциональных преобразователей 29 и 30. Числа т и Ш;, с выходов преобразователей 29 и 30 подаются на входы умножителей 23 и 25. На другие входы умножителей 25, 23 и 24 из вычислителя 2 подаются коэффициенты полинома а , я и а. С выходов умножителей 25, 23 и 24 числа , а, и подаются на вход сумматора 34 куда подается также коэффициент а из вычислителя 2. На выходе сумматора 34 получается, в соответствии с формулой (3), число S . Это число подается в блок 4 сравнения. Одновременно с числом 8ц на выходе сумматора 33 аналогичным образом получается число Sj, которое подается во второй блок 9 сравнения.

Кроме формирователя 3 значений интерполяционного полинома числа mj, и fflj одновременно подаются в блок 10 умножителей, где они служат командой согласно которой отсчеты UCm,) и и(т) из адресов т и т, регистра 10 подаются соответственно в первый 4 и второй 9 блоки сравнения. Модуль разности между значением поли нома и отсчетом сигнала является ошибкой интерполяции. В первом блоке 4 сравнения вычисляется ошибка (ra;)/, во втором блоке9 сравнения - ошибка ,-U(m j)/. Числа сЛ,и d в блоках 4 и 9 сравниваются с допустимым значением ошибки «/д. Если (, (i 1,2), . в обоих блоках 4 и 9 ошибка не превосходит допустимую, то от элемента И на ключ 6 подается команда, по которой вьш1еуказанный процесс повторяется, т.е. сигнальный выход ключа 6 запирается, интервал интерполяции увеличивается на единицу и т.д.

Если ясе хотя бы в одном из блоков 4 и 9 сравнения ошибка интерполя1 ии превзойдет допустимую, то с выхода элемента И поступит другая команда (фиг, 6а, б),по которой отсчет U переписывается в адрес О, т.е. ,, ; отсчет U переписывается в адрес 1, т.е. U,Uj, а текущий отсчет и записывается в адрес 2, что означает ..; новое значение Uj, записывается в элемент 14 памяти в вычислителе 1; число элемента 16 памяти в качестве нового значения а передается в элемент 20 памяти вычислителя 2; разность D, с выхода вычитателя 12 записывается в элемент 16 памяти в вычислителе 1;

Uj-Ue

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

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

tffЛ

IZ

r

/r-j

.Z

.

и I-

21

K-rOj

.5

/f

1±

/7

/5

.

r Ж

is

СЮ O.

т

Uo

и

о 1 2 . .

-г

.

К-/ К

Фмг.5

tlk

Q 1 2

0 I г

Фиг.6

UK

.

K1 К

1 г

К