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

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

Реферат

 

Изобретение относится к области электросвязи, а именно к технике сжатия дискретных сообщений для их передачи и хранения, таких как преобразованные к цифровому виду речевые, звуковые, телевизионные, факсимильные и т.п. сообщения. Способ заключается в предварительном формировании аппроксимирующих кодируемых последовательностей (АКмП), их кодировании, определении и сравнении длины каждой аппроксимирующей кодированной последовательности (АКнП) с предварительно заданной предельно допустимой длиной, стирании АКмП, для которых длины соответствующих им АКнП превышают предельно допустимую длину, выборе из оставшихся АКмП наиболее близкой к кодируемой последовательности и принятии ее в качестве кодированной последовательности двоичных символов. Устройство для осуществления способа состоит из блока идентификации, блока вычисления статистических параметров, первого и второго блоков нормализации, первого, второго и третьего регистров нормализующего сдвига, первого и второго регистров правого сдвига, вычитателя, компаратора, первого, второго и третьего блоков коммутации, сумматора, первого и второго блоков памяти параметров кодирования, регистра кодового интервала, первого и второго регистров левого сдвига, регистра нижней границы кодирования, а также из вновь введенных блока памяти кодируемой последовательности, блока памяти АКмП, коммутатора, блока выбора, блока памяти АКнП, блока сравнения, блока памяти предельно допустимой длины. Технический эффект, достигаемый при их реализации, состоит в уменьшении времени передачи кодированной последовательности по каналу связи с одновременным уменьшением требуемого объема памяти устройств хранения кодированной последовательности. 2 с. и 8 з.п. ф-лы, 27 ил.

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

Заявляемые изобретения могут быть использованы для уменьшения времени передачи кодированной последовательности двоичных символов по каналу связи или для уменьшения требуемого объема устройств хранения кодированной последовательности двоичных символов.

Известен способ сжатия кодируемой последовательности из символов упорядоченного m-ичного алфавита в кодированную последовательность двоичных символов, описанный, например, в книге: Р. Фано. "Передача информации. Статистическая теория связи". - М.: Мир, 1965, стр. 94-101. Он заключается в записи кодируемых последовательностей, состоящих из символов упорядоченного m-ичного алфавита, в порядке убывания их вероятностей, последовательного объединения кодируемых последовательностей, начиная с менее вероятных, в два подмножества, имеющие приблизительно одинаковые суммы вероятностей входящих в них кодируемых последовательностей. Данным подмножествам соответствуют нулевые и единичные символы кодированных последовательностей двоичных символов. Последовательное объединение кодируемых последовательностей в два подмножества выполняется до тех пор, пока каждой из кодируемых последовательностей не будет соответствовать уникальная кодированная последовательность двоичных символов, Известен также способ сжатия кодируемой последовательности из символов упорядоченного m-ичного алфавита в кодированную последовательность двоичных символов описанный, например, в книге: Р.Е. Кричевский. "Сжатие и поиск информации". - М.: Радио и связь, 1988, стр. 5. Он заключается в записи кодируемых последовательностей, состоящих из символов упорядоченного m-ичного алфавита, в порядке убывания их вероятностей и назначении более вероятным кодируемым последовательностям более коротких кодированных последовательностей двоичных символов.

Недостатком известных способов сжатия кодируемой последовательности из символов упорядоченного m-ичного алфавита в кодированную последовательность двоичных символов является большое время передачи кодированной последовательности двоичных символов по каналу связи или большой требуемый объем устройств хранения кодированной последовательности. Это обусловлено тем, что известные способы не способны сжимать кодируемую последовательность, имеющую вероятность P ее появления, в кодированную последовательность двоичных символов длины L бит менее чем значение P logP, что описано, например, в книге: Р. Е. Кричевский. "Сжатие и поиск информации". - М.: Радио и связь, 1988, стр.6.

Известные устройства сжатия кодируемой последовательности из символов упорядоченного m-ичного алфавита в кодированную последовательность двоичных символов описаны, например, в книге: О. И. Лагутенко. "Модемы. Справочник пользователя". - С-Пб.: Издательство "Лань", 1997, стр. 218-226. Данные устройства включают блоки подсчета частости появления символов упорядоченного m-ичного алфавита в кодируемой последовательности и блоки кодирования символов упорядоченного m-ичного алфавита в двоичные символы. Информационные входы блоков кодирования символов упорядоченного m-ичного алфавита в двоичные символы соединены с информационными входами блоков подсчета частости появления символов упорядоченного m-ичного алфавита в кодируемой последовательности и являются входами данных устройств. Выходы блоков подсчета частости появления символов упорядоченного m-ичного алфавита в кодируемой последовательности соединены с управляющими входами блоков кодирования символов упорядоченного m-ичного алфавита в двоичные символы. Работа данных устройств заключается в последовательном отображении символов упорядоченного m-ичного алфавита кодируемой последовательности в кодированную последовательность двоичных символов по правилу, учитывающему вероятности появления символов упорядоченного m-ичного алфавита, подсчитываемыми блоками подсчета частости появления символов упорядоченного m-ичного алфавита в кодируемой последовательности.

Недостатком известных устройств сжатия кодируемой последовательности из символов упорядоченного m-ичного алфавита в кодированную последовательность двоичных символов является большое время передачи кодированной последовательности двоичных символов по каналу связи или большой требуемый объем устройств хранения кодированной последовательности двоичных символов. Это обусловлено тем, что известные устройства не способны сжимать кодируемую последовательность, имеющую вероятность P ее появления, в кодированную последовательность двоичных символов длины L бит менее чем значение P logP, что описано, например, в книге: Р.Е. Кричевский. "Сжатие и поиск информации". - М.: Радио и связь, 1988, стр. 6.

Наиболее близким по своей технической сущности к заявленному способу сжатия кодируемой последовательности из символов упорядоченного m-ичного алфавита в кодированную последовательность двоичных символов является известный способ, описанный в патенте США N 4652856 МПК⁶ H 03 М 7/30 от 24.03.87. Способ-прототип сжатия кодируемой последовательности из символов упорядоченного m-ичного алфавита в кодированную последовательность двоичных символов заключается в том, что предварительно устанавливают двоичное значение нижней границы кодирования длиной 2w двоичных разрядов, где w 2, и двоичное значение кодового интервала длиной w двоичных разрядов. Двоичное значение нижней границы кодирования длиной 2w двоичных разрядов устанавливают, равным двоичному числу, состоящему из w нулевых двоичных разрядов в целой его части и из w нулевых двоичных разрядов в дробной его части и двоичное значение кодового интервала длиной w двоичных разрядов устанавливают, равным двоичному числу, состоящему из единичного значения в целой его части и w-1 нулевых двоичных разрядов в дробной его части.

Последовательно, начиная с первого и до последнего, считывают очередной символ кодируемой последовательности, состоящей из k символов, где k 2, упорядоченного m-ичного алфавита, где m 2, и идентифицируют его с i-ым, где i=1, 2,..., m, символом упорядоченного m-ичного алфавита.

Затем вычисляют статистические параметры очередного символа кодируемой последовательности, для чего в части кодируемой последовательности, предшествующей очередному символу кодируемой последовательности, определяют двоичное число n_i его появлений, сумму Q_j двоичных чисел появлений символов кодируемой последовательности, предшествующих очередному символу кодируемой последовательности в упорядоченном m-ичном алфавите, сумму Q_m двоичных чисел появлений символов кодируемой последовательности, предшествующих последнему символу в упорядоченном m-ичном алфавите и двоичное число N появлений всех символов упорядоченного m-ичного алфавита.

После чего нормализуют вычисленные статистические параметры N, n_i, Q_i и Q_m очередного символа кодируемой последовательности выполнением следующей последовательности действий: устанавливают нормализованное значение очередного символа кодируемой последовательности, равным значению последовательно сдвинутого в направлении старших разрядов двоичного числа N появлений всех символов упорядоченного m-ичного алфавита в части кодируемой последовательности, предшествующей очередному символу кодируемой последовательности, на такое число разрядов, при котором нормализованное значение будет находиться в предопределенном диапазоне значений. Затем устанавливают нормализованное значение очередного символа кодируемой последовательности, равным значению последовательно сдвинутого в направлении старших разрядов на разрядов двоичного числа n_i появлений очередного символа кодируемой последовательности в части кодируемой последовательности, предшествующей очередному символу кодируемой последовательности. После чего устанавливают нормализованное значение суммы очередного символа кодируемой последовательности, равным значению последовательно сдвинутой в направлении старших разрядов на разрядов суммы Q_i двоичных чисел появлений символов кодируемой последовательности, предшествующих очередному символу кодируемой последовательности в упорядоченном m-ичном алфавите, в части кодируемой последовательности, предшествующей очередному символу кодируемой последовательности. Далее устанавливают нормализованное значение суммы очередного символа кодируемой последовательности, равным значению последовательно сдвинутой в направлении старших разрядов на разрядов суммы Q_j,m двоичных чисел появлений символов кодируемой последовательности, предшествующих последнему символу в упорядоченном m-ичном алфавите, в части кодируемой последовательности, предшествующей очередному символу кодируемой последовательности.

Нижний предел предопределенного диапазона значений устанавливают равным двоичному числу 0.11, а верхний предел предопределенного диапазона значений устанавливают меньшим двоичного числа 1.1.

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

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

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

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

Благодаря перечисленной совокупности существенных признаков способ-прототип по сравнению с известными аналогами способен сжать кодируемую последовательность, имеющую вероятность P ее появления, в кодированную последовательность двоичных символов длины L бит сколь угодно близкой к значению P logP.

Недостатком способа-прототипа является большое время передачи кодированной последовательности двоичных символов по каналу связи или большой требуемый объем устройств хранения кодированной последовательности. Это обусловлено тем, что способ-прототип не способен сжимать кодируемую последовательность, имеющую вероятность P ее появления, в кодированную последовательность двоичных символов длины L бит менее чем значение P logP, что описано, например, в книге: Р.Е. Кричевский. "Сжатие и поиск информации". - М.: Радио и связь, 1988, стр. 6.

Наиболее близким по своей технической сущности к заявленному устройству сжатия кодируемой последовательности из символов упорядоченного m-ичного алфавита в кодированную последовательность двоичных символов является известное устройство, описанное в патенте США N4652856 МПК⁶ H 03 М 7/30 от 24.03.87. Известное устройство-прототип включает блок идентификации, вход которого является входом устройства. Выход блока идентификации подключен к информационному входу блока вычисления статистических параметров, выход двоичного числа N_j появлений всех символов упорядоченного m-ичного алфавита, в части j-ой аппроксимирующей кодируемой последовательности, предшествующей очередному символу j-ой аппроксимирующей кодируемой последовательности которого подключен к информационному входу первого блока нормализации, выход суммы Q_j,m двоичных чисел появлений символов j-ой аппроксимирующей кодируемой последовательности, предшествующих последнему символу в упорядоченном m-ичном алфавите в части j-ой аппроксимирующей кодируемой последовательности, предшествующей очередному символу j-ой аппроксимирующей кодируемой последовательности, выход суммы Q_j,i появлений символов j-ой аппроксимирующей кодируемой последовательности, предшествующих очередному символу j-ой аппроксимирующей кодируемой последовательности в упорядоченном m-ичном алфавите в части j-ой аппроксимирующей кодируемой последовательности, предшествующей очередному символу j-ой аппроксимирующей кодируемой последовательности, выход двоичного числа n_j,i появлений очередного символа j-ой аппроксимирующей кодируемой последовательности в части j-ой аппроксимирующей кодируемой последовательности, предшествующей очередному символу j-ой аппроксимирующей кодируемой последовательности блока вычисления статистических параметров, подключены к информационным входам, соответственно, первого, второго и третьего регистров нормализующего сдвига. Управляющие входы каждого из регистров нормализующего сдвига объединены и подключены к выходу первого блока нормализации. Выход идентификации очередного символа j-ой аппроксимирующей кодируемой последовательности с последним символом упорядоченного m-ичного алфавита блока вычисления статистических параметров подключен к управляющему входу третьего блока коммутации. Выход первого регистра нормализующего сдвига подключен к первому информационному входу компаратора, выходы второго и третьего регистров нормализующего сдвига подключены к первым входам, соответственно, первого и второго регистров правого сдвига и дополнительно к первым информационным входам, соответственно, первого и второго блоков коммутации. Вторые информационные входы первого и второго блоков коммутации подключены к выходам, соответственно, первого и второго регистров правого сдвига. Выход компаратора подключен к управляющим входам первого и второго блоков коммутации. Выход первого блока коммутации подключен к первым входам вычитателя и сумматора, второй вход вычитателя подключен ко второму информационному входу компаратора и выходу регистра кодового интервала. Выход второго блока коммутации подключен к первому информационному входу третьего блока коммутации, второй информационный вход которого подключен к выходу вычитателя. Выход третьего блока коммутации подключен к информационным входам второго блока нормализации и первого регистра левого сдвига. Выход второго блока нормализации подключен к управляющим входам первого и второго регистров левого сдвига. Информационный вход второго регистра левого сдвига подключен к выходу сумматора, второй вход которого подключен к выходу регистра нижней границы кодирования. Второй информационный вход регистра нижней границы кодирования подключен к выходу первого блока памяти параметров кодирования, выход первого регистра левого сдвига подключен к первому информационному входу регистра кодового интервала, второй информационный вход которого подключен к выходу второго блока памяти параметров кодирования. Выход записи второго регистра левого сдвига является выходом устройства, выход перезаписи второго регистра левого сдвига подключен к первому информационному входу регистра нижней границы кодирования. Блок вычисления статистических параметров, второй блок памяти параметров кодирования и первый блок памяти параметров кодирования снабжены дополнительным управляющим входом, первый блок нормализации, первый и второй регистры правого сдвига, второй блок нормализации, регистр кодового интервала и регистр нижней границы кодирования снабжены двумя дополнительными управляющими входами, а первый, второй и третий регистры нормализующего сдвига, первый и второй регистры левого сдвига снабжены тремя дополнительными управляющими входами.

Благодаря перечисленной совокупности существенных признаков, устройство-прототип по сравнению с известными аналогами способно сжимать кодируемую последовательность, имеющую вероятность P ее появления, в кодированную последовательность двоичных символов длины L бит сколь угодно близкой к значению P logP.

Недостатком устройства-прототипа является большое время передачи кодированной последовательности двоичных символов по каналу связи или большой требуемый объем устройств хранения кодированной последовательности двоичных символов. Это обусловлено тем, что устройство-прототип не способно сжимать кодируемую последовательность, имеющую вероятность P ее появления, в кодированную последовательность двоичных символов длины L бит менее чем значение P logP, что описано, например, в книге: Р.Е. Кричевский. "Сжатие и поиск информации". - М.: Радио и связь, 1988, стр. 6.

Целью заявляемых изобретений является разработка способа и устройства сжатия кодируемой последовательности из символов упорядоченного m-ичного алфавита в кодированную последовательность двоичных символов, обеспечивающих уменьшение времени передачи кодированной последовательности двоичных символов по каналу связи или уменьшения требуемого объема устройств хранения кодированной последовательности двоичных символов за счет дополнительного сжатия кодируемой последовательности, при котором в кодируемую последовательность вносится погрешность, допустимая для ее получателей. В частности, при сжатии кодируемой последовательности из символов упорядоченного m-ичного алфавита, по своей физической сути являющихся последовательностями элементов изображений, глаз человека не замечает погрешности значений яркости элементов изображений, если эта погрешность не превышает 5...7% от их значений яркости, как описано, например, в книге: А.В.Дворкович, В.П. Дворкович, Ю.Б. Зубарев и др. "Цифровая обработка телевизионных и компьютерных изображений". - М.: Издание международного центра научной и технической информации, 1997, стр. 78.

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

Затем из каждой j-ой, где j = 1, 2,..., Т, аппроксимирующей кодируемой последовательности последовательно, начиная с ее первого символа и до последнего, считывают очередной символ j-ой аппроксимирующей кодируемой последовательности и идентифицируют его с i-ым символом упорядоченного m-ичного алфавита.

Далее вычисляют статистические параметры N_j, n_j,i, Q_j,i и Q_j,m очередного символа j-ой аппроксимирующей кодируемой последовательности, для чего в части j-ой аппроксимирующей кодируемой последовательности, предшествующей очередному символу j-ой аппроксимирующей кодируемой последовательности, определяют двоичное число n_j,i его появлений, сумму Q_j,i двоичных чисел появлений символов j-ой аппроксимирующей кодируемой последовательности, предшествующих очередному символу j-ой аппроксимирующей кодируемой последовательности в упорядоченном m-ичном алфавите, сумму Q_m двоичных чисел появлений символов j-ой аппроксимирующей кодируемой последовательности, предшествующих последнему символу в упорядоченном m-ичном алфавите и двоичное число N_j появлений всех символов упорядоченного m-ичного алфавита.

Затем статистические параметры N_j, n_j,i, Q_j,i и Q_j,m очередного символа j-ой аппроксимирующей кодируемой последовательности нормализуют выполнением следующей последовательности действий. Устанавливают нормализованное значение очередного символа j-ой аппроксимирующей кодируемой последовательности, равным значению последовательно сдвинутого в направлении старших разрядов двоичного числа N появлений всех символов упорядоченного m-ичного алфавита в части j-ой аппроксимирующей кодируемой последовательности, предшествующей очередному символу j-ой аппроксимирующей кодируемой последовательности, на такое число разрядов, при котором нормализованное значение будет находиться в предопределенном диапазоне значений. Нижний предел предопределенного диапазона значений устанавливают, равным двоичному числу 0.11, а верхний предел предопределенного диапазона значений устанавливают, меньшим двоичного числа 1.1. Затем устанавливают нормализованное значение очередного символа j-ой аппроксимирующей кодируемой последовательности, равным значению последовательно сдвинутого в направлении старших разрядов на разрядов двоичного числа n_j,i появлений очередного символа j-ой аппроксимирующей кодируемой последовательности в части j-ой аппроксимирующей кодируемой последовательности, предшествующей очередному символу j-й аппроксимирующей кодируемой последовательности. После чего устанавливают нормализованное значение суммы очередного символа j-ой аппроксимирующей кодируемой последовательности, равным значению последовательно сдвинутой в направлении старших разрядов на разрядов суммы Q_j,i двоичных чисел появлений символов j-ой аппроксимирующей кодируемой последовательности, предшествующих очередному символу j-ой аппроксимирующей кодируемой последовательности в упорядоченном m-ичном алфавите, в части j-ой аппроксимирующей кодируемой последовательности, предшествующей очередному символу j-ой аппроксимирующей кодируемой последовательности. Далее устанавливают нормализованное значение суммы очередного символа j-ой аппроксимирующей кодируемой последовательности, равным значению последовательно сдвинутой в направлении старших разрядов на разрядов суммы Q_j,m двоичных чисел появлений символов j-ой аппроксимирующей кодируемой последовательности, предшествующих последнему символу в упорядоченном m-ичном алфавите, в части j-ой аппроксимирующей кодируемой последовательности, предшествующей очередному символу j-ой аппроксимирующей кодируемой последовательности.

Затем по нормализованным значениям статистических параметров очередного символа j-ой аппроксимирующей кодируемой последовательности j-ые двоичные значения нижней границы кодирования и кодового интервала уточняют выполнением следующей последовательности действий. Если нормализованное значение суммы очередного символа j-ой аппроксимирующей кодируемой последовательности меньше j-ого двоичного значения кодового интервала, то значение переменной устанавливают в нулевое значение, иначе значение переменной устанавливают в единичное значение. Далее, если очередной символ j-ой аппроксимирующей кодируемой последовательности не является последним символом упорядоченного m-ичного алфавита, то j-oe двоичное значение нижней границы кодирования заменяют суммой нормализованного значения суммы очередного символа j-ой аппроксимирующей кодируемой последовательности и j-ого двоичного значения нижней границы кодирования и j-oe двоичное значение кодового интервала заменяют нормализованным значением очередного символа j-ой аппроксимирующей кодируемой последовательности. Иначе, если очередной символ j-ой аппроксимирующей кодируемой последовательности является последним символом упорядоченного m-ичного алфавита, то j-oe двоичное значение нижней границы кодирования заменяют суммой нормализованного значения суммы очередного символа j-ой аппроксимирующей кодируемой последовательности и j-ого двоичного значения нижней границы кодирования и j-oe двоичное значение кодового интервала заменяют разностью между j-ым двоичным значением кодового интервала и нормализованным значением суммы очередного символа j-ой аппроксимирующей кодируемой последовательности. Далее, если переменная имеет единичное значение, то j-ые двоичные значения нижней границы кодирования и кодового интервала сдвигают в направлении их старших разрядов на один разряд.

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

Далее стирают считанную часть j-ого двоичного значения нижней границы кодирования, сдвигают j-oe двоичное значение нижней границы кодирования в направлении старших разрядов на число разрядов его считанной части и дополняют таким же числом нулевых двоичных символов j-oe двоичное значение нижней границы кодирования со стороны младших разрядов.

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

Затем определяют и сравнивают длину L_j каждой j-ой аппроксимирующей кодированной последовательности с предварительно заданной предельно допустимой длиной L_пр. Предварительно заданную предельно допустимую длину L_пр устанавливают не менее w+1 двоичных разрядов. Далее j-ые аппроксимирующие кодируемые последовательности, для которых длины L_j соответствующих им аппроксимирующих кодированных последовательностей превышают предельно допустимую длину L_пр, стирают.

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

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

В заявленном устройстве поставленная цель достигается тем, что в известном устройстве сжатия кодируемой последовательности из символов упорядоченного m-ичного алфавита в кодированную последовательность двоичных символов, содержащем блок идентификации, выход которого подключен к информационному входу блока вычисления статистических параметров, выход двоичного числа N_j появлений всех символов упорядоченного m-ичного алфавита, в части j-ой аппроксимирующей кодируемой последовательности, предшествующей очередному символу j-ой аппроксимирующей кодируемой последовательности которого подключен к информационному входу первого блока нормализации. Выход суммы Q_j,m двоичных чисел появлений символов j-ой аппроксимирующей кодируемой последовательности, предшествующих последнему символу в упорядоченном m-ичном алфавите в части j-ой аппроксимирующей кодируемой последовательности, предшествующей очередному символу j-ой аппроксимирующей кодируемой последовательности, выход суммы Q_j,i появлений символов j-ой аппроксимирующей кодируемой последовательности, предшествующих очередному символу j-ой аппроксимирующей кодируемой последовательности в упорядоченном m-ичном алфавите в части j-ой аппроксимирующей кодируемой последовательности, предшествующей очередному символу j-ой аппроксимирующей кодируемой последовательности, и выход двоичного числа n_j,i появлений очередного символа j-ой аппроксимирующей кодируемой последовательности в части j-ой аппроксимирующей кодируемой последовательности, предшествующей очередному символу j-ой аппроксимирующей кодируемой последовательности блока вычисления статистических параметров, подключены к информационным входам, соответственно, первого, второго и третьего регистров нормализующего сдвига. Управляющие входы каждого из регистров нормализующего сдвига объединены и подключены к выходу первого блока нормализации, выход идентификации очередного символа j-ой аппроксимирующей кодируемой последовательности с последним символом упорядоченного m-ичного алфавита блока вычисления статистических параметров подключен к управляющему входу третьего блока коммутации. Выход первого регистра нормализующего сдвига подключен к первому информационному входу компаратора, выходы второго и третьего регистров нормализующего сдвига подключены к информационным входам, соответственно, первого и второго регистров правого сдвига и дополнительно к первым информационным входам, соответственно, первого и второго блоков коммутации, а вторые информационные входы первого и второго блоков коммутации подключены к выходам, соответственно, первого и второго регистров правого сдвига. Выход компаратора подключен к управляющим входам первого и второго блоков коммутации, выход первого блока коммутации подключен к первым входам вычитателя и сумматора. Второй вход вычитателя подключен ко второму информационному входу компаратора и выходу регистра кодового интервала, выход второго блока коммутации подключен к первому информационному входу третьего блока коммутации, второй информационный вход которого подключен к выходу вычитателя. Выход третьего блока коммутации подключен к информационным в