Патент на изобретение №2159989

(54) СПОСОБ И УСТРОЙСТВО СЖАТИЯ ДАННЫХ С ИСПОЛЬЗОВАНИЕМ АССОЦИАТИВНОЙ ПАМЯТИ

(57) Реферат:

Ассоциативная память используется для выполнения сжатия данных по процедуре Лемпел-Зив-Велч. Техническим результатом является снижение сложности управления сжатием данных. Устройство сжатия данных содержит соответствующие ячейки памяти с полем кода префикса и символьным полем. Содержимое регистра, включающее поле кода и символьное поле, ассоциативно сравнивается с содержимым ячеек памяти для определения наличия совпадения между ними. При обнаружении совпадения адрес совпадения вводится в поле кода регистра, и следующий входной символ вводится в его символьное поле. Этот процесс продолжается до тех пор, пока не будет зафиксировано несовпадение. Код, содержащийся в поле кода регистра, передается в качестве сжатого кода последовательности, и содержимое регистра записывается в следующую пустую ячейку памяти. Следующий цикл инициируется обнулением поля кода регистра, описанные этапы повторяются. 2 с. и 18 з.п.ф-лы, 2 ил.

Область техники
Изобретение относится к сжатию данных и к декомпрессии сжатых данных.

Предшествующий уровень техники
Процедура LZW (Lempel-Zev-Welch – метод сжатия Лемпел-Зив-Велч) представляет собой широко распространенный метод сжатия (уплотнения) и декомпрессии (разуплотнения) данных и используется, например, при осуществлении модемной связи в соответствии со стандартом МККТТ V.42bis. Процедура LZW описана в патенте США N 4558302 от 10 декабря 1985 на “Устройство и способ высокоскоростного сжатия и декомпрессии данных”, переуступленном правопреемнику настоящего изобретения.

Сжатие данных по процедуре LZW использует словарь для запоминания последовательностей символов данных, подаваемых на вход, и поиска введенной последовательности путем сравнения входной последовательности с последовательностями, хранимыми в словаре, для определения совпадения наибольшей длины между ними. Словарь пополняется путем запоминания расширенных последовательностей, содержащих совпадение наибольшей длины, расширяемое посредством последующего символа вводимых данных, который следует за совпадением наибольшей длины. Традиционно словарь сжатия данных реализуется с использованием запоминающего устройства с произвольной выборкой (ЗУПВ). В патенте США N 4558302 высказано предположение (см. столбец 52, строки 30-34), что контекстно-адресуемая или ассоциативная память может быть использована вместо ЗУПВ, что могло бы снизить сложность управления. Однако в указанном патенте не раскрыто, каким образом можно это осуществить. Представляется, что из предшествующего уровня техники неизвестно, каким образом можно реализовать алгоритм сжатия по процедуре LZW на основе ассоциативной памяти.

В патенте США N 4366551 от 28 декабря 1982 на “Систему поиска на основе ассоциативной памяти” раскрыта система запоминания и поиска с использованием ассоциативной памяти. Однако в данном патенте не раскрыто выполнение алгоритма LZW на ассоциативной памяти. Указанный патент N 4366551 был вызван к повторному рассмотрению и преодолен при повторной экспертизе патента N 4558302, в результате которой был выпущен сертификат о повторной экспертизе В 4558302 от 4 января 1994 г.

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

Краткое описание чертежей
Фиг. 1 – блок-схема устройства сжатия, выполненного в соответствии с изобретением.

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

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

Как показано на фиг. 1, устройство сжатия данных 10, выполненное в соответствии с изобретением, содержит контекстно-адресуемую память 11, имеющую N ячеек, каждая из которых имеет поле 12 для хранения кода префикса и поле 13 для запоминания символа. Память 11, кроме того, содержит адресную секцию 14 для обозначения адресов ячеек памяти.

Устройство сжатия 10 осуществляет сжатие последовательности сигналов символов данных по символам [A], имеющим алфавит. Например, в представлениях, соответствующих кодам ASCII (Американский стандартный код для обмена информацией) используется размер алфавита, равный 256. В варианте осуществления устройства сжатия данных 10 с инициализацией последовательностью одного символа первая ячейка [A] памяти 11 инициализируется для помещения в нее последовательностей одного символа [A]. Код префикса в поле 12 ячейки, хранящей последовательность одного символа, устанавливается в нуль, а поле 13 запоминает символ в двоичной форме. Например, в коде ASCII символьное поле 13 имеет ширину 8 бит. Поле кода префикса 12 содержит достаточное число бит для размещения N ячеек памяти 11.

Ячейки памяти 11, начинающиеся с ячейки [A]+1, инициализируются путем установки всех символьных полей 13 в произвольную комбинацию бит, которая не распознается как один из символов алфавита.

Устройство сжатия данных 10, кроме того, содержит регистр 20, имеющий поле 21 для хранения кода и поле 22 для хранения символа. Память 11 работает в ассоциативном режиме или в режиме считывания, когда содержимое регистра 20 сравнивается с содержимым памяти 11. Эта операция обозначена позицией 23. Если содержимое регистра 20 согласуется с содержимым ячейки памяти 11, то на выходе 24 Hit/Miss (“совпадение”/”несовпадение”) фиксируется сигнал Hit (“совпадение”). Адрес ячейки, для которой имело место “совпадение”, получается из адресной секции 14 на выходе 25. Выход 25 является входом для поля кода 21 регистра 20. Если содержимое регистра 20 не найдено в памяти 11, то на выходе 24 формируется сигнал Miss (“несовпадение”).

Память 11 также работает в режиме записи, в котором содержимое поля кода 21 и поля символа 22 регистра 20 записываются в поле кода префикса 12 и поле символа 13, соответственно, памяти 11 в ячейке, адресуемой посредством адресного входа 26. Адреса памяти обеспечиваются на адресном входе 26 с адресного счетчика 31. Входы кода и символа памяти 11 в режиме записи обозначены ссылочными позициями 27 и 28 соответственно. Выбор режима записи/считывания памяти 11 осуществляется посредством входа 30.

Последовательность входных данных символов, подлежащих сжатию, поступает на вход 32 через входной регистр данных 33 в поле символа 22 регистра 20. Сжатый код с устройства сжатия 10 поступает через выходной блок 34 с поля кода 21 регистра 20, Вход 40 нулевого кода используется для обнуления поля кода 21 регистра 20.

Блок логики управления 41 обеспечивает входы для всех компонентов устройства сжатия 10, как показано позицией 42. Блок логики управления 41 принимает сигнал “совпадения”/”несовпадения” с выхода 24 и обеспечивает управление записью/считыванием памяти 11 посредством входа 30 памяти.

В процессе функционирования устройства сжатия 10 в варианте осуществления с инициализацией последовательностью одного символа первые ячейки [A] памяти 11 инициализируются для запоминания всех возможных последовательностей одного символа. В этих инициализированных ячейках поля кода префикса 12 устанавливаются в нуль, а символьные поля 13 устанавливаются в соответствии с двоичными представлениями соответствующих символов алфавита. Адресный счетчик 31 устанавливается в [A]+1. Входной поток символов, подлежащий сжатию, подается на вход 32 и буферизуется во входном регистре данных 33.

Цикл обработки устройства сжатия данных 10 осуществляется следующим образом.

Поле кода 21 регистра 20 обнуляется нулевым кодом 40. Символьное поле 22 запоминает символ, полученный в результате индикации “несовпадения” на выходе 24 в предыдущем цикле. Если, однако, устройство сжатия данных 10 начинает свой первый цикл, то первый символ во входной последовательности помещается в символьное поле 22 из регистра входных данных 33.

Блок логики управления 41 управляет памятью 11 посредством входа 30 для обеспечения работы в ассоциативном режиме. Содержимое регистра 20 сравнивается с содержимым памяти 11 посредством канала 23 и при локализации на выходе 24 регистрируется сигнал “совпадение”, поступающий в блок логики управления 41. Адрес, при котором произошло “совпадение”, загружается в кодовое поле 21 регистра 20, и следующий входной символ загружается в символьное поле 22. Эта процедура повторяется до тех пор, пока не будет зарегистрировано “несовпадение” на выходе 24, поступающее в блок логики управления 41. Когда это происходит, код, содержащийся в поле 21 регистра 20, подается через выходной блок 34 в качестве выходного сигнала сжатого кода для данного цикла.

Блок логики управления 41 осуществляет управление памятью 11 в процессе режима записи посредством входа управления 30, обеспечивая запись кода с входа 27 и символа с входа 28 в поле префикса кода 12 и в символьное поле 13 ячейки, адресуемой адресным счетчиком 31. Адресный счетчик 31 затем получает приращение на единицу, а кодовое поле 21 обнуляется с помощью нулевого кода 40.

Цикл сжатия затем завершается, и устройство сжатия данных 10 готово к выполнению следующего цикла.

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

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

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

На фиг.2 показано устройство декомпрессии данных 50, предназначенное для разуплотнения сжатых выходных кодов устройства сжатия 10 по фиг. 1. Устройство декомпрессии данных 50 принимает выходной сжатый код с выходного блока 34 по фиг.1 и восстанавливает последовательность символов данных. Устройство декомпрессии данных 50 использует ЗУПВ 51 аналогично тому, как это описано в вышеупомянутом патенте США N 4558302. Устройство декомпрессии данных 50 выполнено и работает аналогично тому, как представлено на фиг. 5 упомянутого патента N4558302.

Сжатый код принимается на входе 52 и хранится в регистре входного кода 53. Входной код из регистра 53 поступает на адресный регистр 54 ЗУПВ для обеспечения доступа к ЗУПВ 51 в ячейке, представленной сжатым кодом в адресном регистре 54 ЗУПВ. Каждая ячейка ЗУПВ 51 включает поле кода префикса 55 и символьное поле 56.

Аналогично описанному выше со ссылками на фиг.1, ЗУПВ инициализируется для записи всех последовательностей одного символа. Таким образом, первые ячейки [A] в ЗУПВ 51 инициализируются так, чтобы их поля кода префикса 55 запоминали нуль, а символьные поля 56 – двоичные представления соответствующих символов алфавита.

Устройство декомпрессии данных 50 также содержит адресный счетчик 60, который в начале операции декомпрессии инициализирован в состояние [A]+1. Выходной сигнал адресного счетчика 60 является входным сигналом для адресного регистра 54 ЗУПВ для доступа к ЗУПВ 51. ЗУПВ 51 содержит N ячеек соответственно N ячейкам контекстно-адресуемой памяти 11 на фиг. 1.

ЗУПВ 51 работает в режиме считывания, когда некоторая последовательность символов должна быть восстановлена, и в режиме записи, когда содержимое ЗУПВ обновляется. В режиме считывания код префикса в ячейке, к которой обеспечен доступ посредством регистра адреса 54 ЗУПВ, поступает по каналу 61, а символ с ячейки, к которой обеспечен доступ, поступает в стек магазинного типа 62 по каналу 63. Код префикса по каналу 61 подается на вход регистра адреса 54 ЗУПВ. Стек 62 используется для хранения символов восстанавливаемой последовательности, которые последовательно выталкиваются из стека на выход 64.

В режиме записи ЗУПВ 51 код, подаваемый с регистра предыдущего кода 70 по каналу 71 записывается в поле кода префикса 55 ячейки, доступ к которой обеспечен регистром адреса 54 ЗУПВ. Стек 62 обеспечивает то, что символ посредством входа 72 записывается в символьное поле 56 соответствующей ячейки. При завершении цикла декомпрессии данных код во входном регистре 53 переносится в регистр предыдущего кода 70.

Устройство декомпрессии данных, кроме того, содержит блок логики управления 73, предназначенный для обеспечения входов управления для всех компонентов устройства декомпрессии 50, как показано ссылочной позицией 74. Детектор нуля 75 обнаруживает, когда выходной сигнал кода префикса 61 ЗУПВ 51 нулевой, и передает эту индикацию на блок логики управления 73 по каналу 76.

Для обеспечения обработки для “исключительного случая”, описываемого ниже, устройство декомпрессии данных 50 содержит компаратор 80, который сравнивает код в регистре входного кода 53 с содержимым адресного счетчика 60 и передает индикацию на блок логики управления 73 по каналу 81, когда эти величины равны.

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

Входной код в регистре 53 подается на регистр адреса 54 ЗУПВ для получения доступа к ЗУПВ 51. Блок логики управления 73 управляет ЗУПВ 51 в режиме считывания. Символ, запомненный в ячейке, к которой получен доступ, считывается на выход 63 и проталкивается в стек 62. Код префикса с ячейки, к которой получен доступ, считывается на выход 61 и подается на регистр адреса 54 ЗУПВ для адресации следующей ячейки. Эта процедура продолжается, пока детектор нуля 75 не обнаружит, что считанный код префикса равен нулю. Когда это произойдет, последовательность символов, продвинутая в стек 62, выталкивается наружу в обратном порядке с выхода 64 для обеспечения восстановленной последовательности, соответствующей сжатому коду, полученному на входе 52.

Блок логики управления 73 затем управляет ЗУПВ 51 в режиме записи и записывает содержимое регистра предыдущего кода 70 в ячейку ЗУПВ, доступ к которой обеспечен адресным счетчиком 60. Символ верхней части стека 62 записывается в символьное поле 56 данной ячейки посредством выхода 72 стека. Символ, записанный в символьном поле 56, представляет собой первый символ текущей восстанавливаемой последовательности и является символом расширения записываемой последовательности.

В конце цикла декомпрессии данных адресный счетчик 60 получает приращение на единицу, и код в регистре входного кода 53 переносится в регистр предыдущего кода 70. Устройство декомпрессии 50 готово к приему следующего кода.

В первом цикле устройства декомпрессии 50 операция записи не выполняется, поскольку в данном случае нет предыдущего кода в регистре предыдущего кода 70. Кроме того, адресный счетчик 60 не получает приращения в течение этого цикла.

“Исключительный случай” возникает, когда устройство сжатия по фиг.1 выводит код последовательности, которая хранилась в предыдущем цикле устройства сжатия. Сжатый код, полученный устройством сжатия в этом случае, не будет распознан, поскольку устройство декомпрессии еще не запомнило эту последовательность. Исключительный случай возникает, когда входной сжатый код, принятый в регистр 53, равен содержимому адресного счетчика 60.

Обработка в таком исключительном случае выполняется следующим образом. Код в регистре предшествующего кода 70 переносится в адресный регистр ЗУПВ 54 по каналу 90. Стек 62 представляет собой устройство, описанное в упомянутом патенте N 4558302, в котором последний символ, вытолкнутый из стека, все еще находится в верхнем регистре стека. При нормальной обработке этот символ обеспечивает символ расширения и поэтому перезаписывается, когда символы принимаются на входе 63. При рассматриваемом дополнительном режиме обработки, соответствующем вышеописанному “исключительному случаю”, этот символ проталкивается в стек, после чего следуют символы, восстановленные из кода, присутствующего теперь в адресном регистре 54 ЗУПВ. Данная последовательность затем выталкивается из стека 62 для обеспечения восстановленной последовательности на выходе 64. Адресный счетчик 60 обеспечивает доступ к ЗУПВ 51 посредством адресного регистра 54 ЗУПВ, и символ, находящийся теперь на верху стека 62, записывается в символьное поле 56 ячейки, к которой получен доступ. Код, находящийся теперь в регистре предыдущего кода 70, записывается в ее поле кода префикса 55. Код в регистре входного кода 53 затем переносится в регистр предыдущего кода 70, а адресный счетчик 60 получает приращение для завершения цикла обработки для исключительного случая.

Из вышеописанного следует, что способом, аналогичным описанному в патенте N 4558302, последовательность восстанавливается в обратном порядке на выходе ЗУПВ 51 в ответ на поступление входного кода. Стек 62 используется для реверсирования порядка восстановленной последовательности, обеспечивая ее символы в правильной очередности.

Вышеописанный вариант осуществления изобретения был представлена в терминах инициализации памяти 11 на фиг.1 и ЗУПВ 51 на фиг. 2 последовательностями одного символа. Следует иметь в виду, что изобретение также применимо и к случаю, когда используется инициализация последовательностью нулей. В таком варианте осуществления блоки памяти 11 и 51 очищаются и адресные счетчики 31 и 60 начинают отсчет с единицы. Обработка осуществляется аналогично описанному выше, за исключением того, что если символ встретился первый раз, он передается несжатым, так что устройство декомпрессии может сохранять синхронизм с устройством сжатия. Это может быть обеспечено устройством сжатия 10, передающим нулевой код, за которым следует символ, который может затем быть распознан и восстановлен устройством декомпрессии 50. В таком варианте осуществления нулевой код обнаруживается в регистре входного кода 53 с помощью детектора нуля.

Такая передача нулевого кода и символа может выполняться по каналу от символьного поля 22 регистра 20 к выходному блоку 34. Выходной блок 34 будет накапливать нулевой код из поля 21 и символ из поля 22 регистра 20 для обеспечения их передачи на выход. Кроме того, регистр входного кода 53 по фиг. 2 может быть модифицирован для обеспечения передачи одного символа на выход 64 через стек 62. Символ будет храниться в ЗУПВ 51 с нулевым кодом префикса. Адресный счетчик 60 будет соответственно получать приращение для учета этих различий по отношению к вышеописанному варианту осуществления с инициализацией последовательностью одного символа.

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

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

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

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

2. Способ по п.1, отличающийся тем, что дополнительно включает присвоение последовательных адресов для доступа к последовательным пустым ячейкам памяти для предоставления упомянутой следующей пустой ячейки на этапе (и), причем упомянутые последовательные адреса начинаются со следующей пустой ячейки после упомянутых первых ячеек.

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

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

5. Способ по п.4, отличающийся тем, что дополнительно включает присвоение последовательных адресов для доступа к последовательным пустым ячейкам памяти для декомпрессии для предоставления адреса упомянутой следующей пустой ячейки на этапе (ц), причем упомянутые последовательные адреса пустых ячеек начинаются со следующей пустой ячейки после упомянутых первых ячеек упомянутой памяти для декомпрессии.

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

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

8. Способ по п.7, отличающийся тем, что упомянутая дополнительная процедура обработки включает этапы введения упомянутого символа обновления в стек, переноса содержимого регистра предыдущего кода в адресный регистр, выполнения этапов с (т) по (щ) с созданием при этом упомянутой дополнительной расширенной последовательности, выдачи упомянутой дополнительной расширенной последовательности и запоминания ее в памяти для декомпрессии, причем адрес для этапа (ц) обеспечивает упомянутый сигнал сжатого кода для упомянутой дополнительной расширенной последовательности, и продолжения упомянутого способа декомпрессии с этапа (э).

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

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

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

12. Устройство по п.11, отличающееся тем, что дополнительно содержит адресный счетчик для присвоения последовательных адресов для доступа к последовательным пустым ячейкам памяти для предоставления упомянутой следующей пустой ячейки на этапе (и), причем упомянутые последовательные адреса начинаются со следующей пустой ячейки после упомянутых первых ячеек.

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

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

15. Устройство по п.14, отличающееся тем, что дополнительно содержит адресный счетчик для присвоения последовательных адресов для доступа к последовательным пустым ячейкам памяти для декомпрессии для предоставления адреса упомянутой следующей пустой ячейки, причем упомянутые последовательные адреса пустых ячеек начинаются со следующей пустой ячейки после упомянутых первых ячеек упомянутой памяти для декомпрессии.

16. Устройство по п. 14, отличающееся тем, что блок логики управления декомпрессией предназначен для вывода сигналов символов данных из стека в порядке, обратном порядку, в котором сигналы символов данных были введены в стек.

17. Устройство по п. 14, отличающееся тем, что блок логики управления декомпрессией предназначен для обеспечения работы устройства декомпрессии в дополнительном режиме обработки, вызываемом, когда принятый сигнал сжатого кода не имеет соответствующей последовательности, запомненной в памяти для декомпрессии, причем блок логики управления декомпрессией в упомянутом дополнительном режиме обработки предназначен для создания дополнительной расширенной последовательности, содержащей последовательность, соответствующую сигналу сжатого кода в регистре предыдущего кода, расширенной упомянутым символом обновления, вывода упомянутой дополнительной расширенной последовательности с выводом при этом последовательности, соответствующей упомянутому принятому сигналу сжатого кода, и запоминания упомянутой дополнительной расширенной последовательности в памяти для декомпрессии, причем упомянутый принятый сигнал сжатого кода обеспечивает сигнал сжатого кода, соответствующий упомянутой запомненной дополнительной расширенной последовательности.

18. Устройство по п.17, отличающееся тем, что блок логики управления декомпрессией в упомянутом дополнительном режиме обработки предназначен для введения упомянутого символа обновления в стек, переноса содержимого регистра предыдущего кода в адресный регистр, выполнения этапов с (у) по (щ) для создания при этом упомянутой дополнительной расширенной последовательности, выдачи упомянутой дополнительной расширенной последовательности и запоминания ее в памяти для декомпрессии, причем адрес для этапа (ш) обеспечивает упомянутый сигнал сжатого кода для упомянутой дополнительной расширенной последовательности, и продолжение цикла декомпрессии с этапа (э).

19. Устройство по п.18, отличающееся тем, что признаки с (д) по (к) определяют цикл сжатия, причем устройство сжатия выполняет текущий цикл сжатия, следующий за выполнением предыдущего цикла сжатия, и обеспечивает упомянутый сигнал сжатого кода, когда устройство сжатия в текущем цикле сжатия обеспечивает сигнал сжатого кода расширенной последовательности, введенной в ассоциативную память посредством признака (и) предыдущего цикла сжатия.

20. Устройство по п.18, отличающееся тем, что дополнительно содержит адресный счетчик для присвоения последовательных адресов для доступа к последовательным пустым ячейкам памяти для декомпрессии для предоставления адреса упомянутой следующей пустой ячейке на этапе (ш), причем упомянутые последовательные адреса начинаются со следующей пустой ячейки после упомянутых первых ячеек, и средство для сравнения принятого сигнала сжатого кода в регистре входного кода с содержимым адресного счетчика, при этом блок логики управления декомпрессией предназначен для вызова упомянутого дополнительного режима обработки в соответствии с результатом сравнения принятого сигнала сжатого кода в регистре входного кода с содержимым адресного счетчика.

РИСУНКИ

MM4A Досрочное прекращение действия патента Российской Федерации на изобретение из-за неуплаты в установленный срок пошлины за поддержание патента в силе

Дата прекращения действия патента: 19.12.2003

Извещение опубликовано: 10.05.2005 БИ: 13/2005