CN101069354B - 信息压缩编码装置、其解码装置、及其方法 - Google Patents

Abstract

本发明的目的在于对音频信号、图像信号的采样串提高使用LZ77、LZ78、LZW等词典的编码方法的压缩率。在本发明中，将各采样集中在MSB侧(73)，按每字符大小(例如8比特)N_C的字符C1(i)从MSB侧分割，对于不满N_C的分割部分加入虚比特“0”，作为N_C设为1字符(74)。此外，有时各采样中的低位比特也可以忽略，对于各C1(i)生成将可忽略的比特以及虚比特的各位设为“0”并将有效比特(位)设为“1”的掩码数据M1(i)(75)，使用M1(i)对C1(i)和词典中的索引j的字符串中的各字符D(j)进行比较，从而调查C1(i)的有效位部分一致的情况，如果一致则视作C1(i)和D(j)一致。

Description

信息压缩编码装置、其解码装置、及其方法

技术领域

本发明涉及使用LZ等词典对信息进行压缩编码的装置、其解码装置、及其方法和程序以及记录介质。

背景技术

近年来，在将字符串数据、声音信号数据或图像信息数据通过通信路径传输的情况下，或记录在信息记录介质中的情况下，使用信息压缩编码来减少数据的信息量。

存在将一定数的单位的比特视为1字符，以字符串的重复作为模型来进行信息压缩的编码方法(例如，参照非专利文献1)。在这样的编码方法中有LZ77、LZ88、LZW等方法(例如，参照非专利文献1、非专利文献2)。

以字符串的重复作为模型的信息压缩编码方法不仅被用作文本文件等的压缩编码，而且也用作调制解调器信号、图像信号的编码方法。

图1A表示通过LZ77方法进行的字符串的信息压缩编码装置的例子，图1B中表示其解码装置的例子。在LZ77方法的编码装置中，词典注册部分12在词典部分13中保持一定量的来自输入端子11的输入字符串。一致搜索部分14对新输入的字符串和词典部分13内过去的字符串进行比较。码生成部分15在一定字符数以上，将最长一致的字符串(最长一致字符串)的词典部分(缓冲区)13上的位置(索引)、其一致的长度、输入字符串中的最长一致字符的接着的1字符(不一致字符)作为码，对输出端子16输出。此外，码生成部分15在最长一致字符串的长度小于一定的字符数的情况下，输出表示不一致的码，例如缓冲区上的位置(索引)0以及一致的长度0的码和该一致长度小于一定字符数的输入字符串的前端的1字符。

例如图1C所示，词典部分13在其一端连接先读取缓冲区17，作为整体构成滑动缓冲区(slide buffer)。从先读取缓冲区17的一端，在图中为右端，依次存储输入字符串，先读取缓冲区17满了后，从先读取缓冲区17的左端开始对于字符串的一致搜索处理。码被输出后，最长一致字符串的长度的字符或1字符被从词典部分13的左端废弃，词典部分13的右端存储最后被编码的字符串或1字符。此外，相应地在先读取缓冲区17的右端存储输入字符串。

在LZ77方法的解码装置，信号解析部分22判别来自输入端子21的输入码是否是表示不一致的码。如果不是表示不一致的码，则信号解析部分22将输入字符串分离为位置信息(索引)、一致连续长度、不一致的1字符(不一致字符)。字符串取得部分23基于位置信息和一致连续长度从词典部分24中读出对应的字符串。此外，字符串合成部分25将从词典部分24中读出的字符串和不一致字符合成，并作为解码字符串输出到输出端子26。进而，词典注册部分27将解码字符串存储在词典部分24中。词典部分24是滑动缓冲区，字符串被以与图1A中的词典部分13相对地相同状态被保持。

信号解析部分22在被输入表示不一致的码的情况下，将接着的不一致字符原样输出，同时存储在词典部分24中。

对LZ77进行了改进的编码方法有LZSS、ZIP等。在ZIP等中，将由LZ77得到的码输出进一步通过熵编码的一种即霍夫曼编码进行压缩。

图2A中表示使用代表的LZ78方法的字符串的信息压缩编码装置的例子，图2B中表示其解码装置的例子。在LZ78编码中，从词典部分31为空的状态开始处理。一致搜索部分32对从输入端子11新输入的字符串和注册在词典部分31中的字符串进行比较。码生成部分33将与最长一致的最长一致字符串对应的词典部分31的索引和与接着的不一致的输入1字符对应的索引作成组，作为码对输出端子16输出。此外，词典注册部分34在每次输出码时，将在所述最长一致字符串中加上了接着的1字符的字符串新注册在词典部分31中。词典部分31不是滑动缓冲区而是固定的。图2A的编码装置在输入的字符不在词典部分31中的情况下，将表示不一致的特殊的索引和1字符原样作为码输出。

在图2B所示的LZ78解码装置中，词典部分941是与编码所使用的词典部分31的初始状态相同的初始状态。换言之，词典部分941从空的状态开始处理。码解析部分942将输入码分离为最长一致字符串的索引和接着的1字符的不一致字符索引。字符串取得部分943使用索引从词典部分941中取出一致字符串和不一致字符。字符串合成部分25通过将取出的一致字符串和不一致字符合成来对字符串进行解码，并输出到输出端子26。此时，词典注册部分944通过与编码装置进行的方法相同的方法，将在最长一致字符串中加入了不一致字符的1字符的字符串新注册到词典部分941中。这样，将解码装置的词典部分941的内部状态和编码装置的词典部分31的内部状态保持相同。

在LZ78编码中，词典部分31、941被构成为数结构。在词典内搜索是否注册了与输入字符串相等的要素时，已知用散列函数对字符串进行压缩等，从而使搜索高速化的方法。

图3A表示LZW的编码装置，图3B表示其解码装置。LZW的编码装置的词典部分35中预先注册了有限数的初始字符(数据)。一致搜索部分36对输入的字符串和注册在词典部分35中的字符串进行比较。而且，一致搜索部分36将最长一致的最长一致字符串和与该字符串对应的词典部分35内的索引输出到码生成部分37。码生成部分37将词典部分35内的索引作为码从输出端子16输出。此外，码生成部分37将最长一致字符串输出到词典注册部分38。该字符串的前端字符C_F被附在临时保持在前一缓冲区38a内的前一最长一致字符串的最后，并被注册在词典部分35中。换言之，前一次编码的字符串和本次编码的字符串的前端字符C_F被作为一个连续字符串注册在词典部分35中。

接着，说明图3B的解码装置。码解析部分946从来自端子21的输入码中依次取出最长一致字符串的索引。字符串取得部分947从词典部分945中读出与取出的索引对应的字符串。字符串合成部分948将从词典部分945读出的字符串作为解码字符串输出到输出端子26。同时，词典注册部分949将本次解码的字符串的前端字符C_F附在前一缓冲区949a内的前一次解码的字符串之后，并注册在词典部分945中。

另一方面，作为用于声音信号数据(数字采样值串)的允许失真的压缩编码方法有MP3、AAC、TwinVQ等。作为用于图像信息数据(采样值)的压缩编码方法有JPEG等。也有不允许失真的可逆的编码(污损编码)技术(例如参照非专利文献3)。而且容易编辑加工的浮点形式的数据的可逆压缩也很重要。特别是将浮点形式音频信号仅分为整数串和其余(差分)部分的尾数部分中可能为非0的比特，分别进行编码来提高压缩效率(例如，参照非专利文献4)。

对于原来的采样串的各采样s0(i)作为增益共同地乘以实数G而得到的采样s1(i)为s1(i)＝s0(i)×G。通过二进制表现或IEEE-754形式的二进制浮点表现来表现乘以该实数G而得到的采样s1(i)，经常将这些数字采样串进行编码。如图4所示，作为IEEE-754标准化的浮点形式为32比特，从高位比特起由极性1比特、指数部分8比特、尾数部分23比特构成。将极性设为S，将指数部分8比特所表示的值以十进制数设为E，将尾数部分的二进制数设为M时，该浮点形式的数值以绝对值表现二进制数表示为式子(1)。

[式1]

${(-1)}^S\×1.M\×2^{E-E_0}$    (1)

根据IEEE-754，决定为E₀＝2⁷-1＝127，式(1)中的E-E₀能够取

-127≤E-E₀≤128

的范围的任意值。但是，在E-E₀＝127的情况下全部定义为“0”，在E-E₀＝128的情况下全部定义为“1”。E-E₀＝n表示从式(1)所表示的值的整数部分的位数(比特数)中减去1后的值，即比最高位的“1”低位比特数。

非专利文献1：Nelson，Gailly(荻原、山口译)「デ一タ压縮ハンドブツク改定第2版」第7章～第9章

非专利文献2：D.Salomon“Data Compression”，pp.101-162(第3章)

非专利文献3：Hans，M.and Schafer，R.W.：Lossless Compression of DigitalAudio，IEEE Signal Processing Magazine，Vol.18，No.4，pp.21-32(2001)

非专利文献4：Dai Yang，and Takehiro Moriya：Lossless Compression forAudio Data in the IEEE Floating-Point Format，AES Convention Paper 5987，AES115th Convention，New York，NY，USA，2003 OCTOBER 10-13

发明内容

在以字符串的重复作为模型的信息压缩编码方法中，由于作为基本的模型的特性，在同样的字符组合重复出现这样的情况下，压缩率提高。

对于音频信号的数字采样值、图像信号的数字采样值、心电波数字采样值、地震波数字采样值等测量信号的数字采样值、线性预测分析的残差信号的数字值、其它的数字值等数字信息，也考虑使用LZ等词典来进行压缩编码。但是，现实中出现同样的组合(数字值)的情况比较少，很多情况下得不到所希望的压缩率。

本发明的目的在于提供一种解决该问题的信息压缩编码装置、其解码装置、及其方法程序和记录介质。

根据本发明，对以一定比特数的处理单位所表现的信息使用LZ等词典的信息压缩编码方法中，将已知有效比特位数(以下称作有效位长)的输入信息和注册在词典中的信息进行比较，如果输入信息中的所述有效位长的比特全部一致，则将该注册信息的索引作为输入信息的码的至少一部分输出。

如果仔细观察以二进制表现的信息、以“0”和“1”的二值排列表现的信息的信息集合，则注意到在各信息中偏向于该二值中的一个的情况比较多。以往，搜索输入信息与词典的注册信息完全一致的信息。但是，在本发明中，在有偏向的信息中的重要部分即构成输入信息的比特中，至少搜索相当于有效位的部分的比特与词典中的注册信息一致的信息，一致的该索引被码输出。从而，通过搜索而发现相同索引的情况增多，换言之，输出同一索引的码的情况增多，压缩率相应比以往提高。

附图说明

图1A是表示以往的LZ77编码装置的功能结构的方框图，图1B是表示其解码装置的功能结构的方框图，图1C是表示由词典部分以及先读取缓冲区连接的滑动缓冲区构成的状态的图。

图2A是表示以往的LZ78编码装置的功能结构的方框图，图2B是表示其解码装置的功能结构的方框图。

图3A是表示以往的LZW编码装置的功能结构的方框图，图3B是表示其解码装置的功能结构的方框图。

图4是表示IEEE-754浮点串的图。

图5是表示实施例1(实施例A-3)的编码装置的功能结构例子的方框图。

图6是表示实施例1(实施例A-3)的编码装置的处理步骤的例子的流程图。

图7是表示图6中步骤S4的具体处理步骤的例子的流程图。

图8是表示实施例1(实施例A-3)的掩码LZ77以及掩码LZ78的解码装置的功能结构例子的方框图。

图9是表示实施例1(实施例A-3)的掩码LZ77以及掩码LZ78的解码装置的处理步骤的例子的流程图。

图10是表示实施例1(实施例A-3)的掩码LZW的解码装置的功能结构例子的方框图。

图11是表示实施例1(实施例A-3)的掩码LZW的解码装置的处理步骤的例子的流程图。

图12A是表示实施例A-1的处理步骤的一部分的流程图，图12B是表示实施例A-1的评价部分42c的功能结构例子的方框图。

图13A是表示实施例A-4的掩码LZW中的词典部分43以及掩码计算部分48’的例子的方框图，图13B是表示实施例A-4的掩码LZW中的码生成部分49的一部分具体功能结构例子的方框图。

图14A是表示实施例A-1至A-3中的掩码LZ77的词典部分43和先读取缓冲区65以及有效位信息缓冲区的关系例子的图，图14B是表示实施例A-4以及A-5中的掩码LZ77的词典部分和先读取缓冲区和有效位信息缓冲区的关系例子的图。

图15A是表示每个可变长度采样中比特数不同的情况下的输入采样串的例子的图，图15B是将各输入采样排列在LSB侧并变换为单位处理信息的例子的图，图15C是将各输入采样排列在MSB侧并变换为单位处理信息的例子的图，图15D是将各输入采样排列在LSB侧并按每单位处理信息的比特数N_C切出的例子的图，图15E是将各输入采样排列在MSB侧并按每单位处理信息的比特数N_C切出例子的图，图15F是将各输入采样排列在LSB侧并在比有效位靠近MSB侧附加虚比特(dummy bit)而将比特数扩展的例子的图，图15G是将各输入采样排列在MSB侧并在比有效位靠近LSB侧附加虚比特而将比特数扩展的例子的图。

图16A是表示各输入采样为一定大小的比特长并且各采样的有效位数短于比特长的情况下的掩码LZ方法的单位处理信息的变换例子的图，图16B是表示将采样内的有效的比特集中在LSB侧并设定虚比特的掩码的例子的图，图16C是表示将采样内的有效的比特集中在MSB侧并在允许误差的部分设定虚比特的掩码的例子的图，图16D是表示将各输入采样内的有效的比特集中在LSB侧并按比采样字长短的比特数的每单位处理信息的比特数从采样中切出有效比特部分的方法的图，图16E是表示将各输入采样内的有效的比特集中在MSB例并按比采样字长短的比特数的每单位处理信息的比特数从采样中切出有效比特部分的方法的图。

图17是表示实施例2的编码装置的功能结构例子的方框图。

图18是表示实施例2的单位处理串变换部分79的处理步骤的例子的流程图。

图19是表示实施例2的解码装置的功能结构例子的方框图。

图20是表示实施例2的采样串变换部分84的处理步骤的例子的流程图。

图21是表示实施例3的编码装置的功能结构例子的方框图。

图22是表示实施例3的编码装置的处理步骤的例子的流程图。

图23是表示各种采样的整数形式信号及其差分信号的关系例子的图。

图24是表示实施例3的解码装置的功能结构例子的方框图。

图25是表示实施例3的解码装置的处理步骤的例子的流程图。

图26是表示通过对多个二进制表现数除以共同的乘数来提高编码效率地进行变换的具体数值例子的图。

图27是表示通过对多个浮点数除以共同的乘数来提高编码效率地进行变换的具体数值例子的图。

图28是表示实施方式4的编码装置的功能结构例子的方框图。

图29是表示实施方式4的编码装置的处理步骤的例子的流程图。

图30是表示实施方式4的解码装置的功能结构例子的方框图。

图31是表示实施方式4的解码装置的处理步骤的例子的流程图。

图32是表示实施方式5的编码装置的功能结构例子的方框图。

图33是表示实施方式5的编码装置的处理步骤的例子的流程图。

图34是表示实施方式5的解码装置的功能结构例子的方框图。

图35A是表示使单位处理信息串的编码部分变形的部分的功能结构例子的方框图，图35B是表示将单位处理串变换的一部分变形了的步骤例子的流程图。

图36是表示对最长一致字符搜索应用了散列函数处理的功能结构的一部分的方框图。

图37A是表示各采样的比特数不同的采样串的例子的图，图37B是表示单纯将以每4比特作为1字符变换为字符串的例子的图，图37C是表示使用虚比特维持采样间的相关而变换为字符串的例子的图。

图38A是表示用以往方法和本发明的方法将浮点信号压缩的情况下的压缩结果的图，图38B是比较浮点信号的压缩率的图。

具体实施方式

以下参照附图说明本发明的实施例，但附图中对应的部分赋予同一参照号并省略重复说明。

[实施例1]

编码结构

说明对已知输入信息(数据)的有效比特位数的信息进行编码的情况。作为输入信息考虑各种信息，输入信息一般不是字符。但是，本发明与图1～图3所示的以往技术同样使用词典进行编码。因此，从容易理解的观点出发，在以下的说明中，将编码对象的输入信息的比特串按每多个比特(例如每8比特)集中而表现为字符。此外，在本实施方式中以使用掩码数据作为有效位信息的情况为例。例如，输入字符(处理单位信息)C1(i)为01010101，其掩码数据M1(i)为11110000。掩码数据M1中的“1”表示字符比特串中的对应位有效，“0”表示对应位非有效或者可以忽略。换言之，在本例中，字符C1(i)中的高位4比特0101表示有效，低位4比特0101表示非有效或者可以忽略。

图5表示实施例1的功能结构。从端子41_C按每一字符依次输入以输入字符C1(i)为前端的输入字符串C1(i+0)～C1(i+K)。从端子41_M按每一字符依次输入与输入字符串C1(i+0)～C1(i+K)对应的掩码数据串(有效位信息)M1(i+0)～M1(i+k)。这里，k是从0其每次增加1的正整数。

在词典部分43中对各索引注册了字符串。在本例中，对各索引j注册了由K_j个字符构成的字符串D(j)(0)～D(j)(K_j-1)。构成与词典的索引j对应的存储区域中注册的字符串的各字符在将k设为0≤k≤K_j-1时，表现为D(j)(k)。将字符串表现为D(j)(k)[k：0≤k≤K_j-1]或D(j)(k)[k：0≤k＜K_j]。

一致搜索部分42在考虑有效位信息串M1(i+0)～M1(i+K_j-1)的基础上，从前端的字符开始比较输入字符串C1(i+0)～C1(i+K_j-1)和词典部分43的第j个索引中注册的字符串D(j)(0)～D(j)(K_j-1)。具体来说，如果第k个字符C1(k)和D(j)(k)的有效位信息M1(i+k)的构成比特中与成为1的比特对应的比特一致，则一致搜索部分42判断为一致。在判断为一致的情况下，一边每次将k增加1，一边搜索有效位部分与输入字符串完全一致的词典部分中注册的字符串中最长字符串的词典索引j。而且，搜索的结果，得到的索引j作为压缩码的至少一部分被输出到输出端子44。

以下，详细表示对字符及其掩码数据的“与”进行掩码处理来搜索至少有效位部分一致的词典注册字符的情况下的实施例。

输入字符C1(i+k)和有效位信息M1(i+k)一边将k从0起每次增加1，一边依次输入掩码计算部分42a中。掩码计算部分42a计算C1(i+k)和M1(i+k)的每个比特的“与”C1(i+k)&M1(i+k)。

此外，有效位信息M1(i+k)也被输入掩码计算部分48。掩码计算部分48计算注册在词典部分43的第j个索引中的字符串D(j)(k)[k：0≤k＜K_j]中的字符D(j)(k)和M1(i+k)的每个比特的“与”D(j)(k)&M1(i+k)。

以下，将字符C1(i)以其有效位信息M1(i)进行了掩码处理的结果的C1(i)&M1(i)称作掩码字符。此外，同样，将字符D(j)(i)以对应的有效位信息M1(i)进行了掩码处理的结果的D(j)(i)&M1(i)也称作掩码字符。

信息一致判定部分42b将来自掩码计算部分42a的各掩码字符和来自掩码计算部分48的各掩码字符一边从k＝0起将k每次增加1，一边依次进行比较。而且，C1(i+k)&M1(i+k)和D(j)(k)&M1(i+k)在k＝0～K_j-1全部一致的情况下，信息一致判定部分42b判定词典索引j中注册的字符串和输入字符串一致。

这相当于在进行C1(i+k)和D(j)(k)的一致判定时，有效位信息M1(i+k)的构成比特中，如果成为1而有效的比特至少一致，则判定为这两个字符一致。

例如，在C1(i+k)为01010101，其掩码数据M1(i+k)为11110000，D(j)(k)为01011010时，C1(i+k)&M1(i+k)为01010000，D(j)(k)&M1(i+k)也为01010000。由此，掩码字符C1(i+k)&M1(i+k)和掩码字符D(j)(k)&M1(i+k)被判定为一致。即，C1(i+k)和D(j)(k)至少相当于有效位的部分的比特一致。

这里，词典部分43中注册了将过去输入的字符串编码输出的字符串。

例如，将过去输入了x字符数的K字符的字符串设为C1(i-x+k)[k：0≤k≤K-1]。从掩码计算部分42a输出的字符串被表示为C1(i-x+k)&M1(i-x+k)[k：0≤k≤K-1]。在该情况下，如果词典部分43的索引j中将过去的字符串注册了x_j字符数，则构成注册的字符串的各字符由下式表示。

D(j)(k)＝C1(i-x_j+k)&M1(i-x_j+k)

如果使用上式，信息一致判定部分42b中的字符串比较归结于求C1(i+k)&M1(i+k)和C1(i-x_j+k)&M1(i-x_j+k)&M1(i+k)为0≤k≤K_j-1全部一致的字符串中K_j最长的字符串所对应的索引j。

一致搜索部分42将字符串的一致长度为规定数以上并且与输入字符串一致的字符数最长的字符串所对应的词典索引至少作为对于输入字符串的压缩码的一部分输出。具体来说，存在仅输出词典索引的情况(指掩码LZW法)，输出词典索引和将被判定为不一致的最初的1字符(指不一致字符)用其掩码数据进行了掩码的掩码不一致字符C1(i+K_j)&M1(i+K_j)的情况(指掩码LZ78法)，输出词典索引、连续一致字符长和掩码不一致字符C1(i+K_j)&M1(i+Kj)的情况(指掩码LZ77方法)。而且在掩码LZ77方法以及LZ78法的情况下，在通过所述一致搜索的字符串的一致长度未达到规定数时，输出表示该情况的码和该字符串的前端的1字符的掩码不一致字符C1(i)&M1(i)。基于信息一致判定部分42b的判定结果，码生成部分49将与所述各编码方法对应的码输出到端子44。

信息一致判定部分42b以及码生成部分49例如分别对应于图1A中的一致搜索部分14以及码生成部分15、图2A中的一致搜索部分32以及码生成部分33、图3A中的一致搜索部分36以及码生成部分37。不同之处在于信息一致判定部分42b以及码生成部分49仅比较两个字符的有效位来进行一致的判定。同样，也可以对LZ法的所述以外的方法应用本发明。在该情况下，其处理根据应用的对应编码方法而不同，词典部分43的功能结构、词典中所保持的内容、索引的输出等也根据对应的编码方法而不同。但是，在任何情况下，如果根据有效位信息而有效的比特至少一致则认为字符一致，搜索最长的一致字符串的情况相同。此外，在解码时，使用有效位信息，判别字符串的字符数和各字符中的有效的比特是相同的。而且，根据各个编码方法进行解码。以下，该对应的编码方法例如是指掩码LZ77方法、掩码LZ78法、掩码LZW法，一般是指掩码LZ编码方法。

解码部分45将从码生成部分49输出的码解码为字符串。词典注册部分46解码的最长一致字符串中加入最长一致字符串的最后的字符C1(i+K_j-1)的下一个掩码字符(掩码不一致字符)C1(i+K_j)&M1(i+K_j)，生成K_j+1字符的字符串。而且，词典注册部分46在词典部分43中的比当前注册了字符串的最大索引大一个的索引中注册生成的字符串。另外，该解码字符串的各字符为

D(j)(k)[k：0≤k＜K_j]，即(C1(i-x_j+k)&M1(i-x_j+k))[k：0≤k＜K_j]。从而，词典索引j_max中注册的新的字符串为在

(C1(i-x_j+k)&M 1(i-x_j+k))[k：0≤k＜K_j]的末尾加入C1(i+K_j)&M1(i+K_j)。

在掩码LZ77以及掩码LZ78的情况下，对解码部分45输入表示一致长度为规定值以下的码时，该掩码不一致字符C1(i)&M1(i)原样被输入词典注册部分46，该掩码不一致字符被注册在词典部分43中的比当前注册了字符串的最大索引大一个的索引中。另外，在掩码LZ77以及掩码LZ78的情况下，编码开始时，词典部分43中未注册任何字符，但在掩码LZW的情况下，在编码开始时，词典部分43中注册了全部的1字符。解码部分45以及词典注册部分46的功能结构以及处理在后面说明。

此外，有效位信息根据需要而由有效位编码部分170编码，作为有效位码由端子171输出。有效位编码部分170将对于多个字符的各有效位信息集中压缩编码，提高编码效果。

编码处理

图6表示实施例1的编码处理步骤的例子。在步骤S1中，字符(处理单位信息)C1(i+k)及其有效位信息M1(i+k)被输入一致搜索部分42(通常通过执行程序而从编码装置内或外部的存储部分中取入)。控制部分47调查是否全部输入字符的步骤S3～S6的处理完成了(步骤S2)。如果未完成，则将处理指针i移动到输入字符中的最初的未处理的字符C1(i)和M1(i)(步骤S3)。掩码计算部分42a计算C1(i+k)&M1(i+k)。信息一致判定部分42b通过掩码计算部分48从词典部分45中搜索与C1(i+k)&M1(i+k)[k：0≤k]一致的掩码字符串。而且，求与最长一致的字符串D(j)(k)&M1(i+k)[k：0≤k＜K_j-1]对应的索引(最长一致索引)j_max(步骤S4)。

该搜索例如通过图7所示的子程序(sub routine)执行(在后面进行其说明)。将与求出的索引j_max对应的字符串解码。该解码的字符串中附加了接着的不一致1字符C1_D或接着的解码前端1字符C_F后的字符串，由对应的掩码数据进行掩码，生成掩码字符串。而且，将该掩码字符串注册在词典部分43中(步骤S5)。在掩码LZW的情况下，码生成部分49输出最长一致索引j_max。在掩码LZ78的情况下，码生成部分49输出最长一致索引j_max和接着的不一致1字符C1(i+K_max)&M1(i+K_max)。在掩码LZ77的情况下，码生成部分49输出最长一致索引j_max、一致字符长K_max和接着的掩码不一致1字符C1(i+K_max)&M1(i+K_max)(步骤S6)。接着，返回步骤S2。在步骤S2如果对于全部字符的处理完成，则该输入字符串的编码处理结束。这里，K_max是注册在词典的第j_max个索引中的字符串的长度(字符数)，表示一致字符长(最长一致的字符串的字符数)。

在掩码LZ77和掩码LZ78的情况下，在步骤S4中一致字符长未达到规定值时，在步骤S5中将该输入字符串的前端字符C1(i)由掩码数据M1(i)进行了掩码的结果注册在当前注册了字符的最大索引的接着的索引中。此外，在步骤S6中，将该掩码不一致字符C1(i)&M1(i)与表示一致字符串少于规定值的码(指不一致索引)一同输出。

在本例中，在词典搜索时，在步骤S4中对于输入字符C1(i)，进行由掩码数据M(i)对有效位长以外的比特进行掩码的掩码处理，但如图6中虚线所示，在输入字符、有效位信息的步骤1之后立即对全部输入字符集中进行掩码处理也可以(步骤S7)。此外，在预先判断C1(i)和C1(i)&M1(i)一定相等的情况下，也可以省略由M1(i)对C1(i)进行掩码的处理。

从上述理解，步骤S3中的指针i的移动，在一致长度为规定值以上的情况下，为从i到i+k_max+1，在掩码LZ77以及掩码LZ78中，在一致长度为规定值以下的情况下，为i+1。在掩码LZW中，规定长度是在词典部分43中在一个索引中初始注册的字符数，不产生一致长度未达到规定值的情况。

图5中所示的控制部分47将指针i保持在寄存器47a中，基于该控制和该指针，进行C1(i)、M1(i)的取入、用于使各部分动作的控制。

搜索处理

参照图7说明图6的步骤S4中的词典搜索处理的具体例子。信息一致判定部分42b首先将词典索引j初始化为0，将最长一致字符数(长)k_max初始化为0，将得到最长一致字符长k_max的索引j_max初始化为0(步骤R1)。接着，调查当前搜索索引j是否为词典部分43内的索引的最大值J以上(步骤R2)。如果不是J以上，则将一致字符数k初始化为0(步骤R3)。调查词典部分43内的第j个索引中注册的字符串中的第k个字符D(j)(k-1)和输入字符串的第k个字符C1(i+k-1)在对应于有效位的比特是否一致。在本例中，使用掩码数据M1(i+k-1)对词典43的索引j中注册的第k个字符D(j)(k-1)和输入字符串的第k个字符C1(i+k-1)进行比较。具体来说，首先取词典字符D(j)(k-1)和掩码数据M1(i+k-1)的每个比特的“与”(步骤R10)。然后，调查索引j的第k个掩码词典字符D(j)(k-1)&M1(i+k-1)和指针i的第k个掩码输入字符C1(i+k-1)&M1(i+k-1)是否相等。(这里，计算掩码输入字符C1(i+k-1)&M1(i+k-1)的处理在步骤R10中进行也可以，在如图6中虚线所示的步骤S7中事先计算也可以。)

确认两掩码字符是否一致(步骤R4)。在一致的情况下，对k加上1而返回步骤R10(步骤R5)。在步骤R4中，如果两者不一致，则调查一致字符数k是否大于当前的最长一致字符长k_max(步骤R6)。如果k大则将最长索引j_max更新为当前的索引j，将最长一致字符长k_max更新为当前的k(步骤R7)。在步骤R6中，在k不大的情况下或步骤R7的处理结束了的情况下，在词典索引j中加上1后返回步骤R2(步骤R8)。这样，在施加了掩码的状态下对各索引j的注册掩码字符串和输入掩码字符串进行比较，直到产生不一致字符为止，按每一字符依次进行调查。然后，在步骤R2中，如果j为索引的最大值J以上，则输出得到此时的最长一致字符数k_max时的索引j_max(步骤R9)。该词典搜索处理对于掩码LZ77、掩码LZ78、掩码LZW的任何一个都可以同样地进行。

在k_max为规定值以上的情况下，从压缩编码装置输出的码，在掩码LZ77以及掩码LZ78中，是最长一致索引j_max、一致字符长k_max(在掩码LZ78中省略k_max)、此时的处理指针i的输入字符串中的最初不一致的1字符C1(i+k_max)(一般表示为C1_D)及其掩码数据M1(i+k_max)(一般表示为M1_D)的各比特的“与”(C1_D&M1_D)。此外，在k_max小于规定值的情况下，从压缩编码装置输出的码是表示不一致的索引(例如背景技术中的说明中索引为0、一致字符数为0：以下称作不一致索引)、该处理指针i的前端输入字符C1(i)(称作不一致输入1字符C1_D)及其掩码数据M1(i)的“与”(C1(i)&M1(i))(称作掩码不一致字符)。

从而，如图5中所示，设有与图1A中的码生成部分15、图2A中的码生成部分33对应的码生成部分49。在掩码LZW的情况下仅输出j_max。为了能够进行图7所示的处理，例如在图5的信息一致判定部分42b中设有分别存储了所述参数j、k_max、j_max、k的寄存器42b_A、42b_B、42b_C、42b_D，并设有进行步骤R2、R4以及R6的判定的判定部分42b_E，而且设置控制处理步骤的控制部分42b_F。该控制部分42b_F也可以由控制部分47兼用。

在实施例1中，词典部分43内的注册字符(信息)和输入字符的比较，调查了字符和词典注册字符在一同被掩码了的状态下是否一致。从而，即使在被掩码的部分存在不一致的比特，也判定两字符一致，作为结果，字符串也被处理为一致。因此，最长一致索引(j_max)被输出的次数多于以往方法，能够提高输出码的压缩率。这样，检测掩码字符的一致C1(i+k)&M1(i+k)＝D(j)(k)&M1(i+k)的处理在全部方式中都相同。而且，在掩码LZW中，将一致字符数最大的索引j_max作为码输出。如果一致字符数多于规定数，则在掩码LZ78中，将j_max和C1_D&M1_D作为码输出。在掩码LZ77中，将j_max和k_max和C1_D&M1_D作为码输出。此外，如果一致字符数少于规定数，则在掩码LZ77和掩码LZ78中，将表示一致字符数少于规定数的索引和C1(i)&M1(i)作为码输出。

在LZ77的情况下，将输出码由解码部分45解码后注册在词典部分43中。在一致字符数为规定以上的情况下，在词典部分43中，在与被码输出的最长一致索引j_max对应的字符串D(j_max)(0)～D(j_max)(k_max-1)中附加掩码不一致字符C1(i+k_max)&M1(i+k_max)的字符串被注册在滑动词典的最新的字符串的存储位置。在一致字符数少于规定数的情况下，在词典部分43中，掩码字符C1(i)&M1(i)被注册在滑动词典的最新的字符串的存储位置。

在LZ78、LZW的情况下，在与被码输出的最长一致索引j_max对应的字符串D(j_max)(0)～D(j_max)(k_max-1)中附加掩码不一致1字符C1(i+k_max)&M 1(i+k_max)的字符串被注册在词典部分43的索引J的位置。在注册之后，J被增加1。

解码结构1

说明实施例1的解码装置。图8表示掩码LZ77、掩码LZ78所应用的解码装置。该结构也可以作为图5所示的编码装置中的解码部分45使用。

码解析部分52将来自输入端子51的输入码分离为最长一致索引j_max、一致字符长k_max(在掩码LZ78中被省略)、掩码不一致1字符(C1_D&M1_D)。索引j_max和一致字符长k_max被输入到信息取得部分53。在掩码LZ77的情况下，信息取得部分53从词典部分54的索引j_max的位置取出一致字符长k_max部分的字符串D(j_max)(k)[k：0≤k＜k_max]。在掩码LZ78的情况下，信息取得部分53取出词典部分54的索引j_max中注册的k_max字符的字符串D(j_max)(k)[k：0≤k＜k_max]。然后，传送给掩码计算部分152和连接部分153。掩码计算部分152通过对索引j_max解码而得的字符串的第k个字符和有效位信息M1(i+k-1)的“与”运算从而生成字符串(D(j_max)(k)&M1(i+k))[k：0≤k＜k_max]，并输入字符串合成部分55。字符串合成部分55在输入的字符串的最后连接来自码解析部分52的掩码不一致字符(C1_D&M1_D)，作为解码字符串对输出端子56输出。此外，连接部分153在从信息取得部分53传送的字符串D(j_max)(k)[k：0≤k＜k_max]中连接来自码解析部分52的掩码不一致字符(C1_D&M1_D)后传送到词典注册部分57。词典注册部分57将从连接部分153输入的字符串注册在词典部分54中(对注册在词典中的字符串D(j_max)(k)[k：0≤k＜k_max]不施加掩码)。在从码解析部分52检测到表示一致字符长小于规定值的码(不一致索引)的情况下，将输入的掩码不一致字符C1_D&M1_D作为解码字符输出到输出端子56，同时使用词典注册部分57注册在词典部分54中。该注册处理与图1B中的词典注册部分27相同。另外，在输入有效位码的情况下，该有效位码在有效位解码部分156中解码有效位信息组。而且，从该有效位信息组将与字符D(j_max)(k)对应的有效位信息M1(i+k)依次输入掩码数据生成部分151。

解码处理1

参照图9说明图8所示的功能结构的处理步骤例子。码解析部分52接收码(步骤S11)。控制部分157调查对全部的码的步骤S13～S19的处理是否完成(步骤S12)。如果未完成，则移动处理指针i_C(步骤S13)。控制部分157判定该指针i_C所指未处理的输入的码B1(i_C)中的索引是否为不一致索引(步骤S14)。如果不是不一致索引，则信息取得部分53取得在该索引j_max所表示的词典54中的索引j_max中注册的字符串(步骤S15)。在掩码LZ77的情况下，从索引所表示的位置取得未处理的输入的码B1(i_C)中的一致字符长k_max部分的字符串。在掩码LZ78的情况下，取得与索引对应的位置中注册的k_max字符的字符串。

对取得的字符串与有效位信息M1(i_C+k-1)进行“与”运算，从而生成字符串(D(j_max)(k)&M1(i+k))[k：0≤k＜k_max](步骤S16)。对该掩码字符串连接掩码不一致1字符而作为解码字符串输出(步骤S17)。

此外，在步骤S15中取得的字符串(未施加掩码的字符串)D(j_max)(k)[k：0≤k＜k_max]中连接掩码不一致的1字符后注册在词典部分54中，然后返回步骤S12(步骤S18)。

在步骤S14中判断是不一致索引时，将由码解析部分52分离的掩码不一致1字符作为解码字符输出。进而，将该掩码不一致1字符注册在词典部分54中，返回步骤S12(步骤S19)。在步骤S12中如果对于全部码的处理完成，则结束对于该输入码串的处理。图8中的控制部分157依次使各部分工作，而包括存储处理参数i_C的寄存器157a和进行步骤S12、S19的各判定的判定部分157b。

解码结构2

图10中表示对于实施例1中的掩码LZW的解码装置的例子。该情况下，被输入到输入端子51的字符(处理单位信息)串仅是索引j_max。信息取得部分53取出与注册在词典部分58中的该索引j_max对应的字符串D(j_max)(k)[k：0≤k＜k_max]。掩码数据生成部分151生成与各个字符D(j_max)(k)对应的有效位信息M1(i+k)。掩码计算部分152进行有效位信息M1(i+k)和对应字符D(j_max)(k)的逻辑运算，生成字符串(D(j_max)(k)&M1(i+k))[k：0≤k＜k_max]，作为解码字符串输出到输出端子56。在有效位信息作为有效位码被输入到端子51’中的情况下，如图中虚线所示，由有效位解码部分156解码后得到有效位信息。

此外，由信息取得部分53取得的字符串也被输入到词典注册部分59。如果新的字符串被解码并输出，则词典注册部分59在临时保持在前一缓冲区59a中的前一个从词典部分取出的字符串D(j_max’)(k)[k：0≤k＜k_max’]之后，连接新解码的(从词典部分取出的)字符串的前端字符C_F＝D(j_max)(0)并注册在词典部分58中。而且，词典注册部分59将解码字符串D(j_max)(k)[k：0≤k＜k_max]临时保持在前一缓冲区59a中。

解码处理2

图11表示该掩码LZW的解码处理步骤的例子。首先，信息取得部分53取入码输入(步骤S11)。控制部分157调查全部码的步骤S13～S19的处理是否完成(步骤S12)。如果未完成则移动处理指针i_C(步骤S13)。步骤S11～S13与图9所示的情况相同。在掩码LZW中，接着信息取得部分53从词典部分58中取出与码B1(i_C)的索引j_max对应的字符串D(j_max)(k)[k：0≤k＜k_max]。词典注册部分59将字符串D(j_max)(k)[k：0≤k＜k_max]临时保持在前一缓冲器59a中(步骤S17)。通过与各个字符D(j_max)(k)对应的有效位信息M1(i+k)和D(j_max)(k)的“与”运算，生成字符串(D(j_max)(k)&M1(i+k))[k：0≤k＜k_max]，作为解码字符串从输出端子56输出(步骤S18)。

新的字符串被解码输出后，词典注册部分59在临时保持在前一缓冲器59a中的之前刚从词典部分取出的字符串D(j_max’)(k)[k：0≤k＜k_max’]之后连接新解码的(从词典部分取出的)字符串的前端字符C_F＝D(j_max)(0)，然后注册在词典部分58中。而且，词典注册部分59将解码字符串D(j_max)(k)[k：0≤k＜k_max]临时保持在前一缓冲器59a中并返回步骤S12(步骤S19)。

从以上叙述可理解，实施例1的解码装置相对于以往的LZ77、LZ78、LZW各方式的解码装置、词典部分的结构、进行掩码计算的部分以及词典中注册的内容不同。

[实施例1变形]

以下说明实施例1的各种变形例。

先叙述的实施例1的说明所使用的具体例在以下称作实施例A-3。在该实施例A-3中，在掩码LZ77、LZ78的情况下，如图5中所示，在对输入字符串以及词典中注册的字符串两者施加了掩码M1(i+k)的状态下，进行字符串的一致判定。此外，掩码计算部分42a求对不一致字符C1_D通过其掩码数据M1_D进行了掩码处理的掩码不一致字符C1_D&M1_D，换言之不一致字符中的非有效的位(比特)部分为固定值(在所述例子中为“0”但也可以为“1”)字符的信息。而且，将表示最长一致的字符串的词典索引j_max和掩码不一致字符C1_D&M1_D作为码输出。解码部分45取出与词典部分43的词典索引j_max对应的字符串D(j_max)(k)[k：0≤k＜k_max]。此外，词典注册部分46将连接了掩码不一致字符C1_D&M1_D的字符串注册在词典部分43中。

在词典搜索中，搜索提供了C1(i+k)&M1(i+k)＝D(j)(k)&M1(i+k)，[k：0≤k＜K_j]的最长的K_j的词典索引j。这里，D(j)(k)中注册的内容是过去输入了x_j字符数的字符串。从而，如前所述，构成该字符串的各字符能够表示为D(j)(k)＝C1(i-x_j+k)&M1(i-x_j+k)。

即，词典搜索相当于搜索提供C1(i+k)&M1(i+k)＝C1(i-x_j+k)&M1(i-x_j+k)&M1(i+k)，[k：0≤k＜K_j]的最长的K_j的词典索引j。

此外，在解码端，输出在字符串D(j_max)(k)&M1(i+k)[k：0≤k＜k_max]中连接掩码不一致字符C1_D&M1_D的字符串。

以下，关于对该实施例A-3的变形实施例，主要说明与实施例A-3不同之处。

实施例A-1

在该实施例A-1中，在对输入字符串以及词典中注册的字符串两者都施加了掩码M1(i+k)的状态下进行字符串的一致判定。而且，将最长一致的词典索引j_max和不施加掩码的不一致字符C1_D本身的信息作为码输出。因此，如图5中虚线141所示，字符C1(i+k)也被输入码生成部分49。而且，码生成部分49将字符C1(i+k)作为不一致字符C1_D输出(在A-3中输出掩码不一致字符C1_D&M1_D)。

解码部分45从词典部分43取出与词典索引j_max对应的字符串D(j_max)(k)[k：0≤k＜k_max]。词典注册部分46将连接了不一致字符C1_D本身的字符串注册在词典部分43中。从而，在词典部分43中注册未进行掩码处理的字符串。

换言之，在词典搜索中，搜索提供C1(i+k)&M1(i+k)＝D(j)(k)&M1(i+k)，[k：0≤k＜K_j]的最长的K_j的词典索引j。这里，D(j)(k)中注册的内容是过去输入了x_j字符数的字符串所对应的字符串，该字符串的各字符能够表示为D(j)(k)＝C1(i-x_j+k)。

即，词典搜索相当于搜索提供C1(i+k)&M1(i+k)＝C1(i-x_j+k)&M1(i+k)，[k：0≤k＜K_j]的最长的K_j的词典索引j。

此外，在解码端，不是掩码计算部分152的输出，如图8中虚线157’所示，输出在从词典部分54取得的字符串D(j_max)(k)[k：0≤k＜k_max]中连接如图8中括号所示从码解析部分52取出的不一致字符C1_D的字符串。

在该实施例A-1中，词典部分43内注册的字符不被掩码。但是，输入字符串和词典中注册的字符串(词典字符串)都在施加掩码的状态下被比较，选择一致长度最长的词典字符串。因此，存在得到多个最长一致索引j_max的情况。在该情况下，在得到同一j_max的词典字符串中，选择与输入字符串的距离(例如数值的情况下，两数值之差)最小的词典字符串。这是选择最接近输入字符串的词典字符串。

例如，在图7中的步骤R6中，如果判定为k大于k_max，如图12A所示，调查k是否与k_max相等(步骤R12)。如果相等，则计算此时的输入字符串C1(i+n)[n：0≤n≤k-1]和词典字符串D(j)(n)[n：0≤n≤k-1]的距离。而且，将该距离与j_max对应存储在存储部分中，移动到步骤R8(步骤R13)。在步骤R12中，如果k与k_max不相等则转移到步骤R8。作为这些结构，例如图12B所示，在图5中的信息一致判定部分42b和码生成部分49之间设置评价部分42c。评价部分42e设置执行步骤R12的判定部分42C_A、执行步骤R13的距离计算部分42C_B、存储与各j_max的距离对应的存储部分42C_C、选择存储部分42C_C中的多个j_max中距离最短者的选择部分42C_D。另外，图7中的步骤R7的j_max更新也对存储部分42C_C中的j_max进行。

实施例A-1的说明为掩码LZ77或掩码LZ78的情况。在掩码LZW的情况下，不需要图10中的掩码计算部分152以及图11中的步骤S18中的掩码处理。

实施例A-1’

在实施例A-1中，解码端不进行掩码处理而输出D(j_max)(k)[k：0≤k＜k_max]和C1_D。在实施例A-1’中，掩码计算部分158(图8中以虚线表示)计算对来自码解析部分52的不一致字符C1_D(图8中括号所示)以掩码数据M1_D进行了掩码处理的掩码不一致字符C1_D&M1_D。字符串合成部分55输出在来自掩码计算部分152的掩码字符串D(j_max)(k)&M1(i+k)[k：0≤k＜k_max]中连接了来自掩码计算部分158的掩码不一致字符C1_D&M1_D的字符串。

另外，在掩码LZW的情况下，与参照图10以及图11的实施例A-3的处理同样。

实施例A-2

如图5的虚线142所示，与实施例A-3不同之处在于将从词典部分43取出的字符D(j)(k)直接输入信息一致判定部分42b。换言之，不使用掩码计算部分48。词典部分43中注册的字符串与实施例A-3同样被进行了掩码。从而，在信息一致判定部分42b中，如果C1(i+k)&M1(i+k)＝D(j)(k)成立则判定两字符一致。

在解码端，如图8的虚线157’所示，信息取得部分53取得的掩码字符串不经由掩码计算部分152而被输入字符串合成部分55。

实施例A-4

实施例A-4与实施例A-3不同之处在于搜索与输入字符C1(i+k)和词典字符D(j)(k)的有效位长的短者一致的索引。

如图13A所示，词典部分43具有存储未被掩码的字符串D(j)(k)[k：0≤k＜K_j]的字符部分43a、存储了各字符串的各字符的有效位信息(例如，掩码数据M_D(j)(k)[k：0≤k＜K_j])的有效位部分43b。在掩码计算部分48’中输入输入字符C1(i+k)的掩码数据M1(i+k)以及与来自词典部分43的词典字符D(j)(k)对应的掩码数据M_D(j)(k)。掩码计算部分48’通过输入的掩码数据的每个比特的“与”来计算一致判定所使用的掩码数据M’。即，掩码计算部分48’计算M’(k)＝M1(i+k)&M_D(j)(k)。此外，掩码计算部分42a计算掩码输入字符C1(i+k)&M’(k)，掩码计算部分48’计算D(j)(k)&M’(k)。而且，C1(i+k)&M’(j)(k)和D(i)&M’(k)被输入信息一致判定部分42b。

作为码输出，同样输出最长一致的字符串的词典索引j_max(掩码LZ77的情况下，还有一致长度k_max)。但是，不一致的字符C1_D不被掩码，输出不一致字符C1_D本身。

在输入字符C1(i+k)的有效位长比词典字符D(j)(k)的有效位长长的情况下，还需要输出接着的数据。例如，在图5中的码生成部分49内设置处理部分49a。图13B表示处理部分49a的功能结构。比较部分49b按构成视作二进制值时的M1(i+k)和M’(k)每个比特来比较掩码数据。这里，在存在M1(i+k)为1且M’(k)为0的比特的情况下，需要另外输出与输入字符C1(i+k)的该比特对应的信息。这里，运算部分49c运算M1(i+k)和M’(k)的每个比特的“异或”。在该运算结果M”(k)＞0的情况下，运算部分49d取出与M”(k)的成为1的比特对应的输入字符C1(i+k)的比特，并输出结果。

这样，是C1(i+k)中的有效位(比特)但D(j)(k)的对应的位(比特)不是有效位的部分的比特与j_max、不一致字符C1_D一同被输出。

在掩码LZW方法的情况下，在码输出时进行与图13B所对应的处理，但不输出不一致1字符C1_D。

在解码装置中，如图8中括号所示并且如点划线所示，对于从信息取得部分53取得的字符串D(j_max)(k)[k：0≤k＜k_j]的各k，使用M1(i+k)和M_D(j_max)(k)补充比特后，计算应输出的比特。即，比较部分154求M1(i+k)^(M1(i+k)&M_D(j_max)(k))＞0的k。而且，对于求出的k，从码解析部分52中取出与M1(i+k)^(M1(i+k)&M_D(j_max)(k))中成为1的比特对应的信息。运算部分155将M1(i+k)^(M1(i+k)&M_D(j_max)(k))中成为1的比特与从码解析部分52中取出的比特信息进行置换。这样得到的掩码信息作为M1’(i+k)被输入掩码数据生成部分151。而且，掩码计算部分152将应通过掩码处理输出的字符串复原。即，计算(D(j_max)(k)&M_D(j_max)(k)&M1(i+k))|M1’(i+k)。另外，A^B表示A和B的每个比特的“异或”。A|B表示A和B的“或”。

此外，不被掩码的不一致字符C1_D由字符串合成部分55合成在通过上述处理得到的字符串中。

对词典部分的注册为信息取得部分53取得的字符串D(j_max)(k)[k：0≤k＜k_j]及其有效位信息M(j_max)(k)[k：0≤k＜k_j]，和不一致字符C1_D及其有效位信息M1_D。

实施例A-4’

在实施例A-4’中，对不一致1字符C1_D用其掩码数据M1_D进行掩码后输出。其它与实施例A-4相同。

实施例A-5

仅说明实施例A-5与实施例A-4的不同。不同之处在于在词典部分43中不是注册了字符D(j)(k)而是注册了其掩码后的字符D(j)(k)&M_D(j)(k)，以及编码输出中不一致字符C1_D的作为掩码字符C1_D&M1_D被输出。解码装置与实施例A-4相同。

在实施例A-1～A-3中，例如，以掩码LZ77为例，如图14A所示，在词典部分43中，在词典部分43中最后注册被输入的规定量的字符串。在图14A中，词典部分43具有与构成的滑动缓冲区连接的先读取缓冲区65。在缓冲区65的字符部分65a中存储以接着应编码的字符为前端的字符串。此外，先读取缓冲区65内的各字符C1(i+k)的有效位信息(在本例中为掩码数据M1(i+k))被存储在有效位部分65b中。

在实施例A-4～A-5中，如图14B所示，词典部分43具有与图14A中的词典部分43注册相同内容的字符部分43a、存储注册在字符部分43a中的各字符D(j)(k)的有效位信息(在本例中，为掩码数据M_D(j)(k))的有效位部分43b。先读取缓冲区65与实施例A-1～A-3的情况同样。另外，在掩码LZ78、掩码LZW的情况下，词典部分43不是滑动缓冲区而是固定缓冲区。

按照实施例A-1、A-1’、A-2、A-3、A-4、A-4’、A-5的顺序，容易得到与词典注册字符的一致。从而，相同的索引j_max被输出的次数增多，压缩效率提高。但是，索引j_max的搜索处理增多。此外，在实施例A-4、A-4’、A-5中，在M1(i+k)^(M1(i+k)&M_D(j)(k))＞0的情况下，输入字符仅对有效位有意义，但作为词典字符也输出不是有效位的比特(串)。从而，压缩效率降低。从而，根据信号的性质，考虑搜索处理数(时间)或压缩效率，选择使用哪个实施例即可。

[实施例2]

实施例2是在声音或音乐等音频信号、图像信号、各种测量信号、线性预测误差信号等数字值的采样串的压缩编码、解码中应用实施例1所示的方法、装置的例子。在实施例1中，前提是各输入字符(信息)为一定比特长，并且其有效位信息已知。在本实施例中，主要说明为了能够应用实施例1而将音频信号等数字值的采样串变换为由规定比特数的字符(信息)构成的处理信息串的单位的处理。

首先，说明进行这样的变换的理由。有时所述采样串的各采样的各比特长不同，不是一定比特长的字符(信息)的字符串(单位处理信息串)。因此，考虑如下的变换方法。

将构成各采样的比特按每一比特单位进行分解，变换为顺序排列的比特串。然后，按成为处理的单位的每1字符长(例如4比特)切出。将切出的1字符长的字符串的重复作为信息压缩编码装置的输入。

音频信号等波形信号的采样串本来就具有邻接的采样间的相关(冗余性)或1采样内的相关(冗余性)等大的性质。但是，在如所述这样的变换方法中，很多情况下原来的采样串具有的性质被损害。

本发明为了将采样间和/或采样内的相关(冗余性)也有效地利用于信息串的压缩，将采样串变换为单位处理信息串以保持相关(冗余性)。首先，示出将采样串变换为单位处理信息(字符)的具体例子。

单位处理信息变换例子1(可变长度采样)

图15A中示出可变长度，即字长(比特数)对每个采样不同的情况下的输入采样串的例子。在输入采样串(s1、s2、...)中的各采样的字长(比特数)L_S为可变长度的情况下，在该状态下需要单位处理信息的比特数一定(固定字符大小)，所以无法应用实施例1的掩码LZ码方法。因此，例如，通过输入采样的最大字长(比特数)L_Smax以上将掩码LZ法的单位处理信息的字长(比特数)N_C设为单位处理信息。

图15B是表示将各输入采样排列在LSB(最低位比特)侧，向单位处理信息变换的例子的图。各输入采样s1、s2、...在LSB侧被排列，在比有效位靠近MSB侧附加虚比特(例如0)，字长(比特数)被扩展。这样，使各输入采样成为同一比特数(单位处理信息的比特数N_C)。

图15C是表示将各输入采样排列在MSB(最高位比特)侧，向单位处理信息变换的例子的图。各输入采样s1、s2、...在MSB侧被排列，在比有效位靠近LSB侧附加虚比特(例如0)，字长(比特数)被扩展。这样，使各输入采样成为同一比特数(单位处理信息的比特数N_C)。

也可以将比输入采样的最大字长L_Smax短的字长(比特数)作为掩码LZ法的单位处理信息的比特数(1字符的大小)来进行变换。图15D是将各输入采样排列在LSB(最低位比特)侧并按每单位处理信息(字符)的比特数(字长)N_C切出例子的图。在本例中，将各输入采样s1、s2、...排列在LSB侧，从LSB侧向MSB侧按掩码LZ处理的每1单位处理信息(1字符)的比特数(字长)N_C切出而分割为单位处理信息(1字符)。此时，在输入采样的字长L_S不是单位处理信息的字长N_C的整数倍的情况下，产生剩余的比特。在MSB侧对该剩余的比特附加虚比特(例如0)直到成为单位字长N_C而变换为单位处理信息。采样s1的比特长L_S大于N_C小于2N_C。因此，通过切出最初的N_C比特并在剩余的比特的MSB侧附加虚比特，从而比特数成为N_C的单位处理信息。另外，不向比单位字长N_C的整数倍靠近的MSB侧附加虚比特。这样切出的单位处理信息(字符)从最初的采样s1的LSB侧向MSB侧，并且从接着的采样s2的LSB侧向MSB侧排列。在图15D对单位处理信息的排列顺序赋予号1、2、3、...、12。在本例中，对第2字符(单位处理信息)、第5字符(单位处理信息)、第12字符(单位处理信息)附加了虚比特。另外，在进行与词典注册字符(单位处理信息)的搜索比较时，虚比特部分被掩码。

图15E是将各输入采样排列在MSB(最高位比特)侧并按每单位处理信息(1字符)的比特数(字长)N_C切出例子。在本例中，将各输入采样s1、s2、...排列在MSB侧，从MSB侧向LSB侧按每单位处理信息(1字符)的字长N_C切出而分割为1字符(单位处理信息)。此时，在输入采样的字长L_S不是单位处理信息的字长N_C的整数倍的情况下，产生剩余的比特。在LSB侧对该剩余的比特附加虚比特直到成为单位处理信息的字长N_C。不向比单位字长N_C的整数倍靠近的LSB侧附加虚比特。各字符(单位处理信息)从最初的采样s1的MSB侧向LSB侧，并且从接着的采样s2的MSB侧向LSB侧排列。在图15E中，对单位处理信息的排列顺序赋予号1、2、3、...、12。在图中，对第2字符、第5字符、第12字符附加了虚比特。另外，在进行与词典注册字符的比较时，虚比特部分被掩码。

图15F、图15G是使用小于输入采样的最大字长(比特数)L_smax的单位字长N_C的情况下的其它变换例子。

在图15F中，将各输入采样s1、s2、...排列在LSB(最低位比特)侧，在比有效位靠近MSB侧附加虚比特(例如0)而将字长(比特数)扩展。在扩展时，赋予虚比特，以使比特数为输入采样的最大字长(比特数)L_Smax以上并且为单位字长N_C的整数倍。接着，从LSB侧向MSB侧按掩码LZ处理的每单位处理信息(1字符)的比特数(字长)N_C切出而分割为单位处理信息(1字符)。

在图15G中，将各输入采样s1、s2、...排列在MSB(最高位比特)侧，在比有效位靠近LSB侧附加固定值例如0的虚比特而将字长(比特数)扩展。在扩展时，赋予虚比特，以使比特数为输入采样的最大字长(比特数)L_Smax以上并且为单位字长N_C的整数倍。接着，从MSB侧向LSB侧按掩码LZ处理的每单位处理信息(1字符)的比特数(字长)N_C切出而分割为单位处理信息(1字符)。

单位处理信息变换例子2(长的一定字长)

图16A表示各输入采样为一定大小的字长(比特长)L_S并且各采样的有效位数L_E短于字长L_S的情况下的掩码LZ方法的单位处理信息(1字符)的变换例子。将掩码LZ方法的单位处理信息(1字符)的比特数N_C取为与输入采样的字长L_S相同的长度。接着，如图16B所示，将采样内的有效比特集中在LSB侧，设定虚比特(例如0)。另外，如图16C所示，将采样s1、s2、...内的有效比特集中在MSB侧，在允许误差的部分设定虚比特(例如0)也可以。

图16D表示将各输入采样的有效的比特集中在LSB侧并按比采样字长L_S短的比特数的每单位处理信息的比特数N_C从采样中切出有效比特部分的方法。在该方法中，首先将各输入采样s1、s2、...的有效比特集中在LSB侧。然后，按比采样字长L_S短的比特数的每单位处理信息的比特数(1字符的大小)N_C从采样s1中切出有效比特的部分。在切出时，在切出的有效的比特部分的比特数比单位处理信息的比特数N_C少的情况下，增加虚比特直到比特数达到N_C。然后，中止对采样s1的切出。然后，从采样s2中按每N_C比特数切出有用的比特的部分(由于对于比有效位部分高位比特不能允许误差)。从最初的采样起依次从该LSB侧向MSB侧进行对于切出的单位处理信息(1字符)的号码附加。

图16E表示将各输入采样内的有效的比特集中在MSB侧并按比采样字长L_S短的比特数的每单位处理信息的比特数N_C从采样中切出有效比特的部分的方法。在该方法中，首先将各采样的有效位部分集中在MSB侧。然后，从最初的采样的MSB侧向LSB侧依次按每单位处理信息的比特数(1字符的大小)N_C切出。在该情况下，即使对于1采样的有效位部分的切出结束，也将允许误差的部分全部掩码，因此对于该全部采样长L_S进行切出。然后，对不是有效位的部分附加虚比特。在虚比特的部分也进行对单位处理信息(1字符)的号码附加。在图16D的例子中，与图15F同样，在增加虚比特时，进行处理，以使有效位以上的单位处理信息字长N_C的整数倍并且附加的虚比特的比特数为最小。另外，也可以仅追加虚比特的字符(单位处理信息)，直到超过最大字。

单位处理变换结构以及处理步骤

图17表示通过掩码LZ法将数字值的采样串压缩编码的功能结构例子，图18表示将采样串变换为单位处理信息串的处理步骤的例子。

从输入端子71_S对存储部分72输入采样串，从输入端子71_M对存储部分72输入每个采样的有效位信息I_ED(步骤S21)。控制部分76调查是否对全部采样的步骤S23～S33的处理结束(步骤S22)。如果未完成，则偏向部分73将未处理采样中的最初的1采样和该采样的比特长L_S以及与该采样对应的有效位信息I_ED从存储部分72取出(步骤S23)。偏向部分73如图15、图16中说明的，将取出的采样串偏向到MSB侧或LSB侧，并保持在缓冲区中(步骤S24)。如图16所示，在采样的字长L_S固定的情况下，偏向有效位部分。例如，根据有效位数、I_ED和最长(固定)比特长L_S对采样进行移位处理从而进行偏向。

控制部分76将采样处理长L初始设定为采样的比特长L_S(步骤S25)。然后，调查采样比特长L是否大于0(步骤S26)。如果L大于0，则调查L是否为单位处理比特数(1字符大小)N_C以上(步骤S27)。在N_C≥L的情况下，成为与图15B、15C、16B以及16C对应的处理，在N_C＜L的情况下，成为与图15D、15E、16D以及16E对应的处理。

在步骤S27中，判断为L≥N_C时，单位比特分离部分74从偏向侧(偏向到LSB侧的情况下为LSB侧，偏向到MSB侧的情况下为MSB侧)，从比特长L的采样中取出单位处理信息的规定比特数(1字符大小)N_C，作为1字符(单位处理信息)输出(步骤S28)。掩码数据生成部分75生成与输出的1字符对应的掩码数据M1(i)(步骤S29)。在该情况下，掩码数据生成部分75中的生成部分75a输出各位(比特)为“1”的掩码数据M1(i)。然后，从采样比特长L减去字符大小N_C，L被更新后返回步骤S26(步骤S30)。

在步骤S27中，判断为N_C＜L时，单位比特分离部分74从偏向侧取出L比特。虚比特赋予部分74a在与取出的L比特的偏向侧相反侧赋予N_C-L比特(对于1字符大小N_C的不足部分)的虚比特，作为1字符(单位处理信息)输出(步骤S31)。换言之在将采样偏向在LSB侧的情况下，虚比特被赋予到取出的L比特的MSB侧。掩码数据生成部分75生成对于输出的1字符的掩码数据M1(i)(步骤S32)。在该情况下，生成部分75b输出与有效位的L比特对应的各比特为“1”，与N_C-L个虚比特对应的各比特为“0”的掩码数据M1(i)。接着，采样比特长L被更新为0后返回步骤S26(步骤S33)。

在步骤S26中，在判定为采样处理长L大于0时，返回步骤S22。在步骤S22中如果对于全部采样的步骤S23至S33的处理完成，则向该单位处理串的变换处理结束。

另外，在步骤S31中，在L＝N_C的情况下，N_C-L＝0，不进行虚比特的赋予。图17中的控制部分76进行采样串等的取入、从存储部分72取出规定采样等，同时使各部分依次动作。在控制部分76内设有作为其控制所需的参数的采样比特长L的存储部分76a、有效位信息I_ED的存储部分76b、字符大小N_C的存储部分76c、以及进行步骤S22、S26、S27中的各判定的判定部分76d、进行N_C-L等运算的运算部分76e等。N_C也可以存储在单位比特分离部分74内。这样，采样串被变换为单位处理信息串(字符串)。

该字符串与对应于各字符的掩码数据M1(i)的串被输入作为实施例1说明的掩码LZ编码部分78。然后，如前所述，进行编码处理，码被输出到输出端子44。而且根据需要，例如按每1024等规定个数的采样的区间(所谓帧)，将表示有效位信息I_ED的码从端子171输出。

采样串变换结构以及处理步骤

图19表示用于将输入码解码并将该解码的信息变换为图17的输入采样串的功能结构。此外，图20表示将字符串(单位处理信息串)变换为采样串的处理步骤的例子。

来自输入端子51的输入码被输入掩码LZ解码部分81。此外，根据需要来自输入端子82的各采样的有效位信息被掩码数据变换部分83变换为每字符(单位处理信息)的掩码数据，并输入掩码LZ解码部分81。来自端子82的有效位信息例如按每帧被输入。掩码LZ解码部分81使用实施例A-1～A-5所述的各种解码装置。有时代替掩码数据变换部分83，输入与图10中的端子51’的输入相当的有效位信息或有效位码。

掩码LZ解码部分81解码的字符串(单位处理信息串)从端子56被输入采样串变换部分84(步骤S41)。控制部分88确认是否对于全部字符(单位处理信息)的变换处理完成(步骤S42)。如果未完成，则控制部分88取得解码后的前端采样的字长(比特长)L_S(步骤S43)。单位比特结合部分87在内部确保L_S比特的存储部分87a。此外，单位比特结合部分87将复原比特数L_D初始化为0(步骤S44)。

控制部分88调查L_D是否小于L_S(步骤S45)。如果L_D小，则单位比特结合部分87从未处理的字符串中取出最初的1字符C3(i)(步骤S46)。复原比特数L_D和1字符的比特数N_C被相加，判断该相加结果是否为采样字长L_S以上(步骤S47)。如果不是L_S以上，则取出的C3(i)从存储部分87a的一端侧依次被写入未被写入的部分(步骤S49)。换言之，在将采样串变换为单位处理信息串时，在从LSB(或MSB)侧依次进行的情况下，对存储部分87a的写入也从LSB(或MSB)侧起进行，从LSB(或MSB)侧将C3(i)存储在已存储的L_D比特之后。

在步骤S49之后，将L_D+N_C作为新的复原比特数L_D，返回步骤S45(步骤S50)。

如果步骤S47的加法值为采样字长L_S以上，则计算L_S-L_D(步骤S51)。从掩码字符C3(i)中的LSB(或MSB)侧在未被写入的部分写入(L_S-L_D)比特，并返回步骤S42(步骤S52)。另外，超过采样比特长L_S的N_C-(L_S-L_D)比特被废弃。废弃的方法可以有各种方法。例如，最初舍弃N_C-(L_S-L_D)比特并写入剩余的比特的方法、N_C-(L_S-L_D)比特也被写入用于复原的存储器然后通过比特移位等来废弃的方法等。

此外，在步骤S45中如果复原比特数L_D小于采样比特长L_S，则返回步骤S42。在步骤S42中如果对于全部字符的处理完成，则向采样串的变换结束。

图19中的控制部分88包括存储各处理所需的参数L_S、N_C、L_D等的寄存器88a、88b、88c、进行x_C+L_D的相加等的运算部分88d、进行步骤S42、S45、S48等判定的判定部分88e等，使字符串的写入、前端采样比特长L_S、存储部分87a的确保等各种处理、各部分依次工作。

在图20的步骤S52的处理中，将超过L_S的N_C-(L_S-L_D)废弃，但在该比特对应于在编码时作为虚比特而赋予的比特的情况下，图19的掩码LZ解码部分81不必对输出的字符串进行掩码处理。即，如图8中虚线157’所示，来自信息取得部分53的输出不进行掩码计算部分152的处理而被输出到字符串合成部分55。而且，字符串合成部分55将从码解析部分52输入的掩码不一致字符和来自信息取得部分53的字符串连接后作为解码字符串输出。此外，如虚线159所示，该输出的字符串由词典注册部分57注册在词典中。

通过采用这样的结构，能够将图19中的掩码LZ解码部分81中的处理简化。

同样，也可以将图10的有效位解码部分156的输出作为对图19的掩码数据生成部分85的输入。在该情况下，能够省略图10的掩码数据生成部分151、掩码计算部分152。具体来说，如图10中虚线所示，将来自信息取得部分53的输出作为解码字符串输出。然后，将有效位信息输出到端子56’。该输出被输入图19的端子56’，也不需要掩码数据变换部分83的处理。

[实施例3]

实施例3对浮点形式采样串的编码、解码、特别是非专利文献4所示的编码、解码中应用了本发明。

编码侧

图21表示其编码装置的例子，图22表示其处理例子。从输入端子91输入IEEE-754标准的浮点形式采样串。整数误差分离部分92将各采样例如分离为24比特、16比特等规定比特数的整数信号Y以及该整数信号和输入采样的差分信号Z(步骤S61)。输入采样串(例如IEEE-754标准的32比特浮点形式的音频信号)是包含小数点以下的小数部分的浮点形式信号。整数化部分93由各采样生成考虑了极性的2的补数表现的整数形式信号Y。差分生成部分94输出变换为浮点形式的信号Y和输入采样的差分。差分信号Z由输入采样的尾数部分的低位(23-n)比特构成。位数计算部分93a对整数形式信号Y的位数n进行计数，作为差分信号Z的有效位信息输出(步骤S62)。这里，使用非专利文献4所记载的方法决定整数形式信号Y的有效位数n，以使2ⁿ≤|Y|＜2⁽ⁿ⁺¹⁾。在非专利文献4中，将整数形式信号的采样设为M，在2^(n-1)≤|M|＜2⁽ⁿ⁾时，尾数部分的高位n-1比特成为0。这等价于本发明中的2ⁿ≤|Y|＜2⁽ⁿ⁺¹⁾时尾数部分的高位n比特成为0。另外，在|Y|＝0时，如后面实施例5中所示，也可以将输入的码小数点信号的32比特全部作为差分信号Z。

来自差分生成部分94的差分信号是输入浮点形式采样的23比特尾数部分的高位侧的通常为0的被除去n比特的(23-n)比特的可变长度采样。图23表示变换为整数形式信号Y和差分信号Z的例子。整数形式信号Y的最长比特数例如为24比特，差分信号Z是比特数L_I最长为23比特、最小为1比特的可变长度信号。

图21的单位处理串变换部分95以与图17相同的结构、与图18相同的处理步骤将可变长度的差分信号Z变换为规定比特数的字符串(单位处理信息串)(步骤S63)。由于从整数形式信号Y的位数n得到差分信号Z的有效位数(23-n)比特，因此n也可称作有效位数信息。掩码LZ方法的1字符(单位处理信息)的比特数N_C可以是作为L_E＝23比特而在图16B或图16C中所示的字符串，或者使1字符的比特数N_C例如为8比特而在图16D或图16E中示出的变换形式。如应用图16B所示的变换形式，则掩码数据M1(i)的高位的n比特成为虚比特，即表示不是有效位的比特。此外，对于差分信号Z的掩码数据M1(i)的生成可以根据整数位数n生成。由于差分信号Z最小为1比特，因此掩码数据最低具有1比特的“1”。差分信号Z的有效位的最大长度为23比特。但是，如果全部差分信号Z中附加1比特的虚比特“0”以使其成为24比特(例如图16E所示)从而变换为字符串，则在将字符大小N_C设为8比特的情况下，能够以N_C＝8单位来变换差分信号Z。同样也可以对差分信号Z应用图15E所示的变换形式。

掩码LZ编码部分96对由单位处理串变换部分95变换的字符串进行编码(步骤S64)。作为该掩码LZ编码的具体数值例子，说明应用了实施例A-3的掩码LZW的情况。在词典部分43(图5)中将可以8比特表现的全部组合预先设定为初始值。

词典部分43的索引所使用的信息量，在初始状态下，例如为9比特。字符或字符串在词典部分43按每个索引注册。在达到可以9比特表现的最大字符串的数的情况下，将索引的表现所使用的比特数每次增加1比特。索引所使用的比特数最大例如为16比特。

依次输入输入字符串C(i+k)以及有效位信息(掩码数据)M(i+k)，搜索词典部分43中注册的字符串中最长的一致字符串。该搜索在图7的步骤R10～R6中进行。码生成部分49将通过搜索得到的最长一致的字符串的词典索引j_max作为码输出。将输入的字符设为C1(i+k)，将其有效位信息(掩码数据)设为M1(i+k)(将k从0起逐渐增加)，将词典部分43中注册的第j个(索引)的字符串的长度设为K_j，将该字符串表示为D(j)(k)[k：0≤k＜K_j]。在该情况下，一致判定是对k为0到K_j-1的全部(k)求具有使C1(i+k)&M1(i+k)＝D(j)(k)&M1(i+k)成立的最长的k的词典索引j_max。

在每次输出码时，在词典中新注册在与前一个输出的码对应的字符串D(j_max’)(k)[k：0≤k＜k_max’]中加入用M1(i+0)对与这一次输出的码对应的字符串的前端的一字符D(j_max)(0)进行了掩码处理的掩码前端字符D(j_max)(0)&M1(i+0)后的字符串。这样，长的字符串逐渐被注册在词典部分中，能够搜索与更长的字符串的一致。

整数形式信号Y由整数编码部分97压缩编码(步骤S64)。该压缩编码利用作为整数值的波形值的相关等，可以通过可逆压缩法高效率地进行压缩编码。合成部分98将整数形式信号的码C_Y和对于来自掩码LZ编码部分96的差分信号Z的编码码C_Z合成。然后，合成部分98将合成的码按每个采样或者每帧作为编码码输出(步骤S65)。

解码侧

图24中示出与图21对应的解码装置的功能结构，图25中示出该处理步骤的例子。分离部分102将来自输入端子101的码C_Y以及码C_Z的组分离为码C_Y以及码C_Z(步骤S71)。整数解码部分103将码C_Y解码为整数形式信号Y(步骤S72)。浮点化部分104将整数形式信号Y变换为浮点形式信号(步骤S73)。

码C_Z被输入掩码LZ解码部分105。位计算部分103a对由整数解码部分103解码的整数形式信号Y的位数n进行计数，位数n作为有效位信息输出到掩码LZ解码部分105(步骤S74)。此外，如虚线所示，也可以在整数解码部分103和掩码LZ解码部分105之间具有掩码数据变换部分106。在该情况下，有效位信息n被输入掩码数据变换部分106。掩码数据变换部分106将(23n)比特作为各采样的有效位，生成各字符(单位处理信息)的掩码数据，然后输出到掩码LZ解码部分105。这里，整数形式信号Y的有效位数n通过与编码时的处理相同的方法决定。即，决定n，以使2ⁿ≤|Y|＜2⁽ⁿ⁺¹⁾。

掩码LZ解码部分105与进行图10以及图11所示的结构以及处理的解码装置相同。掩码LZ解码部分105将码C_Z掩码LZ解码为单位处理信息串(步骤S75)。由掩码LZ解码部分105解码后的字符(单位处理信息)串被输入采样串变换部分107。采样串变换部分107的结构与图19的采样串变换部分84同样。采样串变换部分107使用有效位信息对由掩码LZ解码部分105解码的字符串进行掩码处理。在掩码处理后，除去虚比特而将字符串变换为差分信号Z(步骤S76)。该差分信号Z由各采样可能同为0以外的(23n)比特构成。组装部分107a将差分信号Z变换为浮点的23比特尾数部分信号(步骤S77)。合成部分108将作为尾数部分的差分码Z和解码后的整数形式信号Y的浮点信号合成，输出原浮点信号采样(步骤S78)。

在本例中，对于作为差分信号Z而能够成为0以外的值的可变长度比特串进行掩码LZ编码、解码。但是，也可以对23比特的尾数部分的状态的差分信号Z进行掩码LZ编码、解码。在该情况下，采样长度为固定字长。

[实施例4]

例如，在以通用编码方法进行编码的情况下，如果对输入采样串除以共同的乘数的结果进行编码，则能够提高压缩率。本实施例是对除以该共同乘数而进行编码的方法应用了本发明。先简单说明如果进行共同乘数的除法则能够提高压缩率的情况。

输入信号采样串为x(1)、x(2)、x(3)，如图26A所示，在十进制表现x(1)＝250、x(2)＝50、x(3)＝350的情况下，其二进制表现分别被比较随机地排列“0”和“1”。

采样x(1)、x(2)、x(3)除以共同的数A＝1.5625，则如图26B所示，其商信号y(1)、y(2)、y(3)分别以十进制表现为y(1)＝160、y(2)＝32、y(3)＝224。

分别如图26C所示，商信号y(1)、y(2)、y(3)的二进制表现为“0”连续存在的部分多的排列。从而，能够以高的压缩率将y(1)、y(2)、y(3)编码。但是，也需要送出乘数A。但是，在采样数多并且大部分能够为可高压缩的商信号的情况下，能够较大地减少整体的压缩码量。

图27示出应用于IEEE-754浮点数的采样串的例子。如图27A所示，十进制表现的数值478.4、95.68、669.76的浮点表现的尾数部分的23比特的“1”、“0”的排列都是随机的。但是，它们除以共同乘数2.99时，如图27B所示，其商信号的十进制表现分别为160、32、224。以浮点表现的尾数部分的23比特的“1”、“0”的排列中“0”变得非常多。从而，与图27A这样压缩编码相比，能够以显著高的压缩率来进行编码。

编码侧

参照图28说明实施例4的编码侧。

来自输入端子201的输入信号X＝(x(1)，x(2)，...)是被数字化的采样串，其被输入后(步骤S81)，由区间(帧)分割部分202分割为规定数N个(例如1024个)采样串，虽然未图示，但存储在临时存储部分中(步骤S82)。作为采样串，在声音信号的情况下，考虑以24比特的量化比特数量化的整数采样串或32比特单精度浮点形式采样串等。在彩色图像信号的情况下，是分解为各色信息要素后栅格扫描的像素信息的数字化的采样串。

作为各分割区间的输入信号的采样x(i)(i＝0，1，...，N1)的集合被按每1帧传送到乘数估计部分203。乘数估计部分203对全部采样x(i)(i＝0，1，...，N)估计共同的乘数A(步骤S83)。例如，全部采样x(i)由共同值99.0切割的情况下，为共同的乘数A＝99.0。作为估计该共同的乘数A的方法，考虑多种方法。例如，使用近似共同因素(ACF：ApproximateCommon Factor)的有理近似。这里，采用提供适当的乘数A的方法。

由乘数估计部分203决定的乘数A被传送到除法处理部分204、乘法部分205、乘数编码部分206。

在除法处理部分204中，将由乘数估计部分203传送的乘数A和N个采样x(i)作为输入，计算N个商信号y(i)＝x(i)/A(步骤S84)。此时，y(i)可以是整数形式、浮点形式、固点形式的任何一个。在变换为该决定的表现形式时，也可以进行舍去、舍入、四舍五入、nearest tie to even(至偶数最近连接)等化整处理。

例如，将x(i)变换为倍精度的浮点数，这里变换为64比特的浮点数后除以乘数A。得到的倍精度的商化整为最近的单精度(32比特)的浮点数而作为商信号y(i)。

由除法处理部分204得到的N个商信号串Y＝(y(0)，y(1)，...，y(N1))被传送到商信号编码部分207和本例中的乘法部分205。

在乘法部分205中，将从乘法估计部分203传送的乘数A分别乘以从除法处理部分204传送的N个商信号串Y的各信号y(i)，从而得到复原的N个采样x’(0)，x’(1)，...，x’(N1)(步骤S85)。

此时，复原采样x’(i)被化整为可以32比特的浮点表现来进行表现的值的范围。例如，将y(i)乘以A的结果作为倍精度(64比特)的浮点数保持，将得到的倍精度的乘法结果化整为最近的单精度(32比特)的浮点数而作为x’(i)。得到的采样串X’＝(x’(0)，x’(1)，...，x’(N1))被传送到误差计算部分208。

误差计算部分208从由输入信号取出的N个采样x(0)，x(1)，...，x(N-1)分别减去由乘法部分205传送的N个复原采样x’(0)，x’(1)，...，x’(N-1)，从而得到由N个差分信号z(0)，z(1)，...，z(N-1)构成的差分信号串Z＝(z(0)，z(1)，...，z(N1))(步骤S86)。该差分信号的计算也可以代替使用减法而将x(i)和x’(i)的32比特原样进行以比特为单位的“异或”(xor)。主要是进行x(i)和x’(i)的差分运算即可。

来自该误差计算部分208的差分信号串Z被输入有效位生成部分209以及单位处理串变换部分211。有效位生成部分209求在输入的N个差分信号z(0)，z(1)，...，z(N-1)中的最高位侧具有“1”的比特位置(位)。换言之，求帧内的最大比特长作为有效位信息(步骤S87)。然后，该有效位信息被输入单位处理串变换部分211。单位处理串变换部分211例如与图17所示的功能结构相同，通过图18所示的处理步骤，将差分信号串变换为规定比特数的字符串(单位处理信息串)。然后，单位处理串变换部分211将变换为图15B～图15G、图16B～图16E的其中一个的字符串(单位处理信息串)的字符串和有效位信息输出到掩码LZ编码部分96(步骤S88)。

商信号编码部分207将来自除法处理部分204的商信号串Y进行压缩编码而输出商码C_Y。作为压缩编码的方法，有线性预测编码方法等利用波形值的相关的高压缩率的可逆压缩编码方法(例如参照非专利文献3)或其它的非可逆的压缩编码方法(MPEG4、AAC、TwinVQ等)。掩码LZ编码部分96将来自单位处理串变换部分211的字符串进行压缩编码，作为单位处理码C_Z输出。在该掩码LZ编码部分96中，进行先前叙述的掩码LZ77、掩码LZ78、掩码LZW等掩码LZ编码。有效位编码部分212将表示帧内的最长比特长的有效位信息可逆编码为有效位码C_d。乘法编码部分206对乘数A进行可逆编码，作为乘数码C_A输出(步骤S89)。合成部分98将商信号码C_Y、单位处理码C_Z、有效位码C_d、乘数码C_A按每帧作为一组码C_x输出(步骤S90)。商信号的编码只要在步骤S84之后在何时均可，乘数A的编码只要在步骤S83之后在何时均可，有效位信息的编码也只要在步骤S87之后即可。

解码侧

图30表示实施例4的解码装置的功能结构例子，图31表示处理步骤的例子。

分离部分102将来自端子221的编码数据C_x分离为商信号码C_Y、单位处理码C_Z、有效位码C_d、乘数码C_A(步骤S91)。商信号解码部分222通过与商信号编码部分207的编码方法对应的解码方法，将商信号码C_Y解码为N个商信号y(0)，y(1)，...，y(N-1)(步骤S92)。乘数解码部分223将乘数码C_A解码(步骤S93)。乘法部分224将解码的乘数A分别乘以解码的N个商信号y(0)，y(1)，...，y(N-1)(步骤S94)。有效位解码部分225将有效位码C_d可逆解码，生成有效位信息(表示帧内最长的比特长的信息)(步骤S95)。掩码LZ解码部分105使用所述有效位信息将单位处理码C_Z解码为字符串(步骤S96)。采样串变换部分211将由掩码LZ解码部分105解码的字符串变换为采样串的差分信号z(0)，z(1)，...，z(N1)(步骤S97)。加法部分226将差分信号z(0)，z(1)，...，z(N-1)分别与乘法部分224的输出相加(步骤S98)。帧连接部分227将来自加法部分226的输出信号x(0)，x(1)，...，x(N1)连接，作为解码信号输出(步骤S99)。求y(i)和A的乘法信号Ay(i)的处理和求差分信号采样z(i)的处理哪个先进行都可以。在有效位码C_d或乘数码C_A与前帧相同的情况下，也可以输出表示该情况的少的比特数的码。作为商信号编码部分207使用非可逆压缩编码的情况下，如图28中虚线所示，由解码部分213解码商信号码C_Y，将该解码信号代替除法处理部分204的输出信号y(i)而输入乘法部分205即可。

[实施例5]

下面说明在除以共同乘数来进行压缩编码的方法和非专利文献4所示的浮点信号的编码方法中应用了本发明方法的实施例5。

编码侧

图32表示功能结构例子，图33表示处理步骤的例子。

与实施例4相同，区间分割部分202取入输入信号x(i)(步骤S81)，进行帧分割后存储在存储部分中(步骤S82)。乘数估计部分203估计乘数A(步骤S83)。除法处理部分204将输入信号x(i)除以乘数A而化整在有效位以内(步骤S84)。另外，在乘数A为1时，也可以省略除法处理部分204中的除法处理。在本例中，判定处理部分231内的判定部分231a判定除法处理结果的单位精度浮点数是否是无限大的值、或非标准化值、不能表示为数值的所谓NaA的特殊数值(步骤S110)。以下，将无限大的值、或非标准化值、不能表示为数值的NaA总称为“特殊数值”。如果步骤S110的判定为特殊数值，则开关231b从除法处理部分204侧切换到0信号源231c侧，0信号被提供给整数化部分93(步骤S111)。如果步骤S110的判定不是特殊数值，则步骤S84的除法处理结果被输入到整数化部分93。

整数化部分93由来自判定处理部分231的输入信号生成整数形式信号y(i)(步骤S112)。浮点化部分232将整数形式信号y(i)变换为浮点信号(步骤S113)。乘数部分205对该浮点信号乘以乘数A而将乘法结果进行化整处理(步骤S114)。这里，在判定为特殊数值的情况下，或者y(i)＝0的乘法结果为0的情况下，输入信号(采样)x(i)的32比特原样通过误差计算部分208而被输入单位处理串变换部分95。另外，在乘数A为1时，也可以省略步骤S114的乘法处理。此外，如虚线将步骤S113和S114包围这样，也可以通过对整数信号y(i)乘以浮点的乘数A来进行一次步骤S113和步骤S114。

另一方面，乘数判定部分233判定乘数A是否为1(步骤S115)。如果A＝1，则开关234连接到差分生成部分94，输入信号x(i)被输入差分生成部分94。整数化部分93的位数计算部分93a对整数形式信号y(i)的位数n进行计数，生成有效位信息。该有效位信息n也被输入差分生成部分94(步骤S116)。差分生成部分94与实施例3的编码装置同样，生成由输入信号(采样)x(i)的尾数部分的低位(23n)比特构成的差分信号z_e(i)(步骤S117)。另外，差分信号z_e(i)为可变长度采样。这里，在x(i)为特殊数值的情况，或y(i)＝0的情况下，输入信号(采样)x(i)的32比特被输入单位处理串变换部分95。在步骤S115中，如果乘数A不是1，则开关234被连接到误差计算部分208。误差计算部分208生成输入信号x(i)和乘法部分205的输出信号的差分信号z_d(i)(步骤S118)。

单位处理串变换部分95取得来自误差计算部分208的差分信号z_d(i)或来自差分生成部分94的差分信号z_e(i)，变换为单位处理信息串(步骤S63)。整数编码部分97将整数形式信号y(i)编码为整数码C_Y。掩码LZ编码部分96将单位处理信息串掩码LZ编码为单位处理码C_Z。乘数编码部分206将乘数A编码为乘数码C_A(步骤S119)。合成部分98合成码C_Y、C_Z、C_A并按每帧输出(步骤S65)。

判定部分231a判断x(i)为特殊数值时，设为y(i)＝0。从而，该输入信号(采样)x(i)的32比特通过误差计算部分208被输入单位处理串变换部分95。乘数判定部分233判定为不是A＝1时，从误差计算部分208对单位处理串变换部分95输入该输入信号(采样)x(i)的尾数部分的23比特，判定为A＝1时，从差分生成部分94对单位处理串变换部分95输入该输入信号(采样)x(i)的尾数部分中的低位(23-n)比特。如图15A～图15G所说明的，单位处理串变换部分95能够将这样的可变长度采样变换为单位处理信息串。而且，即使在最大采样长度为32比特的情况下，也同样能够变换为单位处理信息串。

这里，如图35这样，也可以在单位处理串变换部分95前一个使用最高位比特位判定部分235。最高位比特位判定部分235判定该处理区间的输入采样串(差分信号z_d(i)或来自差分生成部分94的差分信号Z_e(i))的不是0的最高位比特位，并作为最高位(比特)信息L_Smax输出到单位处理串变换部分95以及最高位编码部分237。在最高位编码部分237中，将不是0的最高位(比特)的信息编码后输出到合成部分98。

单位处理串变换部分95使用信号的最高位(比特)信息L_Smax将输入的信号(差分信号z_d(i)或来自差分生成部分94的差分信号z_e(i))变换为单位处理串。

此外，在处理区间内，也可以将整数形式信号y(i)的值为0的采样和不为0的采样分开，整理采样的顺序以将其连续输入到掩码LZ编码部分。例如图35B所示，有进行处理的方法。选择来自差分生成部分94或误差计算部分208的处理区间(帧)的最初的输入采样(步骤S131)。判定该采样是y(i)为0的采样还是除此以外的采样(步骤S132)。这里，y(i)为0的采样相当于进行编码的比特有效位为32比特的采样。此外，除此以外的采样相当于要编码的比特有效位小于32比特的采样。如果步骤S132为“是”，则变换为单位处理信息串(步骤S133)。接着，判定是否进行了对于处理区间的最终采样的步骤S132和S133(步骤S134)。如果对于最终采样的处理未结束，则选择接着的采样后返回步骤S132(步骤S135)。在步骤S132中，判定是y(i)不为0的采样后，转移到步骤S134。在步骤S134中，判定为对于最终采样的处理结束后，将该区间的未处理采样，即y(i)不为0的差分信号集中变换为单位处理信息串(步骤S136)。

最高位(比特)信息也可以对于要编码的比特有效位为32比特的采样集合和小于32比特的采样集合分别进行判定。

解码侧

图34表示该实施例5的功能结构例子。该处理步骤与图31所示大致相同。但是，商信号码C_Y对应于整数码C_Y。

分离部分102将输入的码C_X分离为整数码C_Y、单位处理码C_Z、乘数码C_A。整数解码部分103将整数码C_Y解码为整数形式信号y(i)。在整数形式信号y(i)的位数n以及y(i)＝0的情况下，表示该情况的信息作为有效位信息从整数解码部分103输入到掩码数据变换部分106。掩码数据变换部分106将有效位信息变换为每个单位处理信息的掩码数据。换言之，在A＝1的情况下，对于各采样与(23n)比特对应的掩码数据被输入掩码LZ解码部分105，而且在y(i)＝0的情况下，对于该采样与32比特对应的掩码数据被输入掩码LZ解码部分105。掩码LZ解码部分105将单位处理码C_Z进行掩码LZ解码而生成单位处理信息串。乘数解码部分223将乘数码C_A解码为乘数A。在乘数A不是1的情况下，掩码数据生成部分236生成与尾数部分的23比特对应的掩码数据，并输入到掩码LZ解码部分105。

浮点化部分104将解码的整数形式信号y(i)变换为浮点信号。乘法部分224对浮点化部分104的输出乘以乘数A。采样串变换部分107将来自掩码LZ解码部分105的单位处理信息串变换为采样串即差分信号z(i)。加法部分226将差分信号z(i)与乘法部分224的输出相加，该输出被输入到帧连接部分227。另外，在(23-n)比特的采样的情况下，采样串变换部分107中与图24中的对应部分同样，在其高位连接n个0而组装为23比特的尾数部分。在解码整数形式信号y(i)为0的情况下，从采样串变换部分107输出32比特的浮点信号(采样)，其被输入到帧连接部分227。

另外，如图32中虚线所示，也可以将判定处理部分231刚好插入区间分割部分202之后。特殊数值为例外，对于不包含特殊数值的浮点信号，如图32中的虚线238这样，也可以将除法处理部分204的输出侧与整数化部分93直接连接。

[变形实施例]

这里，在掩码LZ编码部分的编码结果的大小大于被输入单位处理串变换部分95的大小的情况下，也可以将原数据与表示不进行掩码LZ编码的信息一同原样输出到合成部分98。

在该情况下，比较对由区间分割部分分割的各区间使用掩码LZ的情况和不使用的情况的数据大小，将大小减小者与选择码一同输出。

在开始各区间的编码时，预先保存掩码LZ编码部分内的内部状态。在压缩后大小不减小的情况下，在进行下一区间的掩码LZ编码处理之前返回到保存了掩码LZ编码部分的内部状态的状态。由此，能够保持编码侧和解码侧的内部状态的同步。

接着，说明每个采样中有效位不同的输入信号的编码中应用的实施例。

例如，在声音信号的编码中，存在使用听觉心理模型等，在从人的听觉特性难以感到失真的部分允许大的失真这样的编码方式。基于该允许的失真的量，提供值的有效位信息。例如图16A所示，输入的采样串的字长一定，例如为31比特。由图17中所示的单位处理变换部分79进行字长分配处理，以成为适于掩码LZ编码部分78中的处理的形式，基于有效位信息来设定掩码数据。

这里，以图16E所示的字符串变换为例，假设1字符的字长为8比特的情况。如图16E所示，输入的信号串基于有效位的信息被集中在LSB侧，按掩码LZ方法的处理单位即每8比特切取而作为字符串排列。此时，在输入信号串的字长不是1字符的字长的整数倍(在目前的例子中为8的整数倍)的情况下，在MSB侧追加值“0”的虚比特以成为8比特的倍数。

此外，生成表示有效位的掩码数据。掩码数据设定为有效比特部分为“1”，允许失真的比特部分以及虚比特部分为“0”。如果将从输入信号切出的第i个字符设为C1(i)，将对应的掩码数据设为M1(i)，则可以将该字符串、掩码数据串作为输入来应用图5所示的实施例1(包含实施例1的变形)的压缩编码方法。

以下，示出应用了实施例A-1(掩码-LZ77)的情况下的具体例子。

将先读取设为256字符(8比特)，将词典部分43(图14A)的缓冲区大小设为65536字符(16比特)。

由此，位置信息(索引)表示为16比特，最大一致长度表示为8比特。另外，这为一例，也可以使用已知的方法进一步高效率地进行处理。例如，也可以应用LZSS来代替LZ77而不损害本发明的有效性。

在先读取缓冲区65(图14A)中的输入字符串C1(i)、有效位信息(掩码数据)M1(i)、以及词典部分43(滑动缓冲区)中注册的字符串中，搜索最长的一致字符串。与通过搜索得到的词典中的最长一致字符串对应的索引、一致长度、不一致的先读取缓冲区中的接着的1字符C1_D作为码输出。

将先读取缓冲区中的字符串表示为C1(i+k)，将有效位信息表示为M1(i+k)[k＝0，1，2，...]，将词典部分(滑动缓冲区)中注册的第j个位置开始的字符串表示为D(j)(k)，将有效位表示为M(j)(k)，将从词典的第j个位置开始的字符串和先读取缓冲区内的字符串的一致长度设为k_max，在一致判定中，对于从k＝0到k＝k_max-1的全部k求具有使C1(i+k)&M1(i+k)＝D(j)(k)&M(j)(k)成立的最长的k_max的词典中的位置j。

在使用实施例A-4代替实施例A-1的情况下，对于从k＝0到k＝k_max-1的所有k，求出具有使C1(i+k)&M1(i+k)&M(j)(k)＝D(j)(k)&M(j)(k)&M1(i+k)成立的最长的k_max的词典中的要素j。

接着，在每次输出码时，从先读取缓冲区中删除接着一致的字符串的不一致1字符，并将接着一致字符的不一致1字符注册在词典部分43中。词典部分43中的最旧的字符串被废弃。

在实施例A-1中，在将一致的字符串C1(i+k)和M1(i+k)[k：0≤k＜k_max]注册在词典部分43(滑动缓冲区)中的情况下，在非可逆的例子中，不是复制一致的先读取缓冲区中的k_max字符的C1(i+k)，M1(i+k)，而是将一致作为码输出的D(j_max)(k)和C1(i+k)的有效位信息M1(i+k)成组追加在词典部分43中。接着，将最长一致的字符串的接着的1字符C1(i+k)(＝C1_D)和M1(i+k)(＝M1_D)追加在先读取缓冲区65中。换言之，如图14A中虚线所示，在词典部分43中也设有存储掩码数据M(i)的掩码部分43c。

在先读取缓冲区65中读入与被删除的相同数的新的输入字符串和对应的有效位信息。

以下表示解码处理。

解码处理对编码处理中进行的各个处理进行对应的逆操作。

如图8中已经说明的，解码装置中作为输入而接受码串和有效位信息。有效位信息由掩码数据生成部分151变换为掩码数据(M1(i)串)。

这样得到的码和有效位掩码数据被输入掩码LZ解码装置中。

掩码LZ解码装置使用码输入和有效位信息(掩码数据)将原来的字符串复原。这样得到的字符串由图19中的采样串变换部分84复原为原来的字长31比特的信号串。

上述中输入字符(单位处理信息)以数值信息为前提。从而，有效位一般是越高位越重要。非有效或也可以忽略的位(比特)是LSB侧。而且在虚比特也偏向于LSB侧的情况下，在该采样的有效位的最高位比特以上，为满足1字符大小所需的连续的比特。另一方面，例如在一般的字符中，也有时即使其构成比特的某一特定比特的1～多个变化，对于信息串的整体也几乎不带来影响。在该情况下，有效位或虚比特不连续。能够将1字符的比特串的中途的比特(位)作为非有效的位来应用本发明。在该情况下，在将字符串变换为采样串时，如图19中虚线所示，由掩码数据生成部分85从每个字符的有效位信息生成掩码数据。然后，选择部分86从输入单位比特结合部分87的字符串中的各字符中仅选择对应的掩码数据的“1”的位(比特)的比特即可。有效位信息由掩码LZ解码部分81或外部提供。

使用散列的高速搜索处理

说明对图6的步骤S4的词典搜索处理使用散列(hash)来进行高速化的具体例子。在图7所示的方法中，将词典索引j从0变化到最大值，将词典中注册的全部字符串与输入字符串进行比较。在不进行掩码处理的以往的LZ编码方法中，已知使用散列函数(hash function)处理来使搜索高速化的方法。但是，在掩码LZ中，由于需要依赖于掩码来搜索同一词典注册字符是否与多个输入字符一致，因此不能原样应用已知的散列函数处理方法。

这里，示出了在词典部分中注册字符串时，将使用考虑了有效位的散列函数处理使搜索高速化的方法应用于掩码LZW中的例子。

考虑将输入字符串与词典部分中注册的内容一致的字符串设为D(j)(k)[k：0≤k＜K_j]，将接着的不一致字符C1(i+K_j)连接的字符串新注册在词典部分的索引J+1中的情况。在已知的散列函数处理法中，例如将j和C1(i+K_j)作为关键(key)来计算散列值，并注册在词典部分内的散列表(hashtable)的对应的位置。

而在本发明中，例如图36所示，在词典部分361内准备散列表362互相不同的掩码数。而且，散列函数运算部分363计算以j和C1(i+K_j)&M作为关键的散列值。由切换部分364切换为与掩码数据M对应的散列表，并注册字符串。这里，M是掩码比特互相不同的掩码数据，在1字符的处理单位为8比特的情况下，在LSB侧集中搜索的情况下，有00000001至11111111的8种。

在进行搜索的情况下，以M(i+k)中1的数作为关键来选择一个散列表，以j和C1(i+K_j)&M(i+k)作为关键来搜索选择的散列表362。

作为有效位信息，例如也可以使用有效位的最高位比特和最低位比特的两个位置信息。在该情况下，例如对要比较的两个字符调查与其中一个的比特位置对应的各比特是否一致，并调查如果一致则接着的各比特是否一致。如果全部一致则认为该2字符一致，如果在中途发生了不一致，则为该2字符不一致即可。

上述编码装置、解码装置也可以分别通过计算机起作用。在该情况下，将用于使计算机具有作为目标的装置(在各种实施例中具有图示的功能结构的装置)的作用的程序或用于使计算机执行该处理步骤(各实施例中所示的步骤)的各过程的程序，从CD-ROM、磁盘、半导体记录装置等记录介质或经由通信线路下载到该计算机内，并执行该程序即可。

[通过本发明能够以高的压缩率将可变长度采样编码的理由]

以下，说明为何根据本发明能够将声音或音乐等音频信号、图像信号、各种测量信号、线性预测误差信号等数字值的采样串变换为能够以高压缩率编码的单位处理信息串。图37A中表示各采样的比特数不同的采样串的例子(或有效比特数不同的采样串的有效比特部分的例子)。在将该采样串变换为每4比特的字符串的情况下进行研究。图37B中表示单纯将以每4比特作为1字符变换为字符串的例子(以往的方法)。图37C中表示使用虚比特变换为字符串，以使不同的采样的比特不包含于一个字符的例子(本发明的方法)。

首先，示出通过本发明的向字符串的变换方法能够期待高压缩率的压缩编码。

在将比特数可变的采样串变换为字符串(在本例中4比特1字符)的情况下，如果单纯按每4比特划分输入的比特串，则成为图37B所示的字符串(y(1)，...)。如果这样划分，则例如y(5)由采样x(1)的最后(LSB侧)的2比特和采样x(2)的最初(MSB侧)的2比特构成。

另一方面，一般通过对音频信号及其它的波形信号等时间序列信号进行采样而得到的数字的采样串多为各采样间的相关大，并且各个采样或采样的块相类似。但是，如上所述，如果变换为包括由不同的采样的LSB侧和MSB侧的比特构成的字符的字符串，则不能使变换后的字符串具有各个采样或采样的块所具有的类似性。从而，在图37B所示的单纯的变换中，成为不能期待高压缩率的编码的字符串。

因此，在本发明中，如图37C所示，不进行向跨越采样的字符串的变换。在本发明中，附加虚比特直到各采样成为单位比特数(在本例中为4比特)的整数倍为止。而且，通过按每单位比特进行划分从而变换为字符串。如果这样将可变长度的采样串变换为一定长度的字符串，则能够使变换后的字符串具有各个采样或采样的块所具有的类似性。从而，能够以高压缩率对基于时间序列信号的数字采样串进行压缩编码。

接着，示出通过本发明的掩码处理提高压缩率的情况。

在每个采样的有效位不同的时间序列信号的采样串的情况下，互相的采样的有效位不同，但包含同一部分的采样多。但是，如果对包含仅有效位部分或虚比特的字符使用以往的搜索完全一致的字符的编码方法，则很多情况不能发现完全一致的字符串。在图37B的字符串中，连续的多个字符之间不存在一致的字符串。在本发明中，将图37C的字符串的y(7)、y(8)、y(9)与过去的字符串进行比较的情况下，对y(9)的后3比特进行掩码处理。换言之，不比较y(9)的后3比特(即使不同也可以)。从而，判断为y(7)、y(8)、y(9)和y(3)、y(4)、y(5)一致。这样，通过使用虚比特和掩码处理，从而能够将有效位不同但包含同一部分的字符串作为相同的字符串，因此发生与过去发生过的字符串相同的字符串的概率升高。从而，能够基于时间序列信号来提高数字采样串的压缩率。

[实验例子]

为了表示本发明的效果，图38A和图38B中示出了对浮点信号的压缩率进行比较的实验结果。输入信号是信号1(96kHz采样，量化比特数24比特)、信号2(96kHz采样，量化比特数24比特)、信号3(48kHz采样，量化比特数24比特)的浮点信号。在本发明的方法中，如图37C所示，进行与图15E相当的排列，将每8比特作为1字符通过实施例3的方法压缩。在以往方法中，在用实施例3对误差信号Z进行编码时，代替本发明，如图37B所示，将有效比特串连连接而将每8比特作为1字符用以往的LZ编码进行编码。另外，将原来的输入信号的大小设为x，将压缩后的大小设为y时，以往的压缩率为(y/x)×100。由图38A、图38B可知，得到了按照本发明的高压缩率。

Claims (23)

1.一种信息压缩编码方法，搜索与以一定比特数的处理单位表现的信息即单位处理信息的串对应的、注册在词典部分中的单位处理信息即词典信息的串，对输入信息进行压缩编码，其特征在于，

所述信息压缩编码方法具有：

一致判定步骤，将由所述输入信息生成的单位处理信息串中的与输入信息的有效位对应的有效比特与词典信息的对应的比特进行比较，如果所述有效比特和对应的比特全部一致，则判定所述单位处理信息和词典信息一致；

搜索步骤，在能够判断为与由所述输入信息生成的单位处理信息的串一致的词典信息的串中，搜索最长的词典信息的串，并求该最长的词典信息的串的索引；以及

输出步骤，输出所述索引或与所述索引对应的码。

2.如权利要求1所述的信息压缩编码方法，其特征在于，具有词典注册步骤，其将包含所述索引所表示的单位处理信息的串的单位处理信息的串注册在词典部分中。

3.如权利要求2所述的信息压缩编码方法，其特征在于，在所述词典注册步骤中，在注册的单位处理信息的量变为多于规定的量的情况下，从最前面注册的单位处理信息开始删除。

4.如权利要求1所述的信息压缩编码方法，其特征在于，

输入信息为采样串，

所述信息压缩编码方法还具有单位处理信息生成步骤，其对于每个采样，将构成采样中的有效位的比特组按每个所述处理单位进行分割，从而生成所述单位处理信息，

在所述单位处理信息生成步骤中，在通过分割而剩余了采样的比特的情况下，或者采样的比特不满处理单位的情况下，对剩余的比特或不满处理单位的采样的比特追加虚比特而作为单位处理信息，并使得追加的虚比特部分不是有效的比特。

5.如权利要求4所述的信息压缩编码方法，其特征在于，

输入信号为浮点形式，

所述信息压缩编码方法还具有：

分离步骤，将输入信号分离为整数形式信号和差分信号；以及

整数形式编码步骤，对所述整数形式信号进行压缩编码，

将所述差分信号的串作为由采样串构成的输入信息，进行所述单位处理信息生成步骤、所述一致判定步骤、以及所述搜索步骤，

在所述输出步骤中，除了输出所述索引之外，还输出在所述整数形式编码步骤中进行了压缩编码的码。

6.如权利要求5所述的信息压缩编码方法，其特征在于，还具有：

判定在所述分离步骤中分离的所述差分信号是否是所述整数形式信号为0的情况下的差分信号的步骤；

如果通过所述判定而判定是整数形式信号为0的情况下的差分信号，则由该差分信号生成第一差分信号串的步骤；以及

如果通过所述判定而判定不是整数形式信号为0的情况下的差分信号，则由该差分信号生成第二差分信号串的步骤，

将所述第一差分信号串和第二差分信号串连接的结果作为由所述采样串构成的输入信息。

7.如权利要求4所述的信息压缩编码方法，其特征在于，还具有：

分解步骤，将由规定的多个输入信号构成的每个分割区间的输入信号串分解为共用的乘数、各输入信号除以该乘数而得的商信号的串、其剩余的差分信号的串；

商信号编码步骤，将所述商信号的串进行压缩编码后输出；以及

乘数编码步骤，将所述乘数编码后输出，

将所述差分信号的串作为由采样串构成的输入信息，进行所述单位处理信息生成步骤、所述一致判定步骤、所述搜索步骤以及所述输出步骤。

8.如权利要求7所述的信息压缩编码方法，其特征在于，还具有：

判定构成在所述分解步骤中得到的所述差分信号的串的差分信号是否是所述商信号为0的情况下的差分信号的步骤；

如果通过所述判定而判定是商信号为0的情况下的差分信号，则由该差分信号生成第一差分信号串的步骤；以及

如果通过所述判定而判定不是商信号为0的情况下的差分信号，则由该差分信号生成第二差分信号串的步骤，

将所述第一差分信号串和第二差分信号串连接的结果作为由所述采样串构成的输入信息。

9.如权利要求4所述的信息压缩编码方法，其特征在于，还具有：

分解步骤，将由规定的多个浮点输入信号构成的每个分割区间的浮点输入信号串分解为共用的乘数、各浮点输入信号除以该乘数而得的信号的串；

整数化步骤，将所述除法处理后的信号变换为整数形式信号；

乘法步骤，求对所述整数形式信号乘以所述乘数而得的浮点信号；

差分信号计算步骤，求在所述乘法步骤中得到的浮点信号和所述浮点输入信号的差分信号；

整数形式信号编码步骤，将所述整数形式信号的串进行压缩编码后输出；以及

乘数编码步骤，将所述乘数编码后输出，

将所述差分信号的尾数部分的串作为由采样串构成的输入信息，进行所述单位处理信息生成步骤、所述一致判定步骤、所述搜索步骤以及所述输出步骤。

10.如权利要求4所述的信息压缩编码方法，其特征在于，还具有：

分解步骤，将由规定的多个浮点输入信号构成的每个分割区间的浮点输入信号串分解为共用的乘数、各浮点输入信号除以该乘数而得的信号的串；

整数化步骤，将所述除法处理后的信号变换为整数形式信号；

浮点化步骤，将所述整数形式信号变换为浮点信号；

乘法步骤，对在所述浮点化步骤中得到的浮点信号乘以所述乘数；

整数形式信号编码步骤，将所述整数形式信号的串进行压缩编码后输出；以及

乘数编码步骤，将所述乘数编码后输出，

在所述乘数为1且所述整数形式信号不为0的情况下，

将作为有效比特而包含由所述整数形式信号的有效位数n决定的所述浮点输入信号的尾数部分的低位即所述浮点输入信号的尾数部分的位数-n的比特的比特组的串作为由采样串构成的输入信息，进行所述单位处理信息生成步骤、所述一致判定步骤、所述搜索步骤以及所述输出步骤，

在所述乘数不为1且所述整数形式信号不为0的情况下，

所述信息压缩编码方法还具有差分信号计算步骤，求在所述乘法步骤中得到的已进行乘法的浮点信号和所述浮点输入信号的差分信号，

将在所述差分信号计算步骤中得到的差分信号的尾数部分的串作为由采样串构成的输入信号，进行所述单位处理信息生成步骤、所述一致判定步骤、所述搜索步骤以及所述输出步骤，

在所述整数形式信号为0的情况下，

将所述浮点输入信号的串作为由采样串构成的输入信号，进行所述单位处理信息生成步骤、所述一致判定步骤、所述搜索步骤以及所述输出步骤。

11.一种信息解码方法，对输入码进行解码而得到解码信息，该输入码包含词典部分的索引中的其中一个索引，该词典部分注册了以一定比特数的处理单位表现的信息即单位处理信息的串，其特征在于，该信息解码方法包含：

有效位信息取得步骤，由所述输入码中包含的信息求表示每个所述单位处理信息的有效比特的信息即有效位信息；

单位处理信息串取得步骤，由包含在所述输入码中的索引取得注册在词典部分中的单位处理信息的串；以及

掩码处理步骤，使用所述有效位信息确定所述取得的单位处理信息串中的有效部分，从而得到解码信息。

12.一种信息解码方法，对输入码进行解码而得到解码信息，该输入码包含词典部分的索引中的其中一个索引，该词典部分注册了以一定比特数的处理单位表现的信息即单位处理信息的串，其特征在于，该信息解码方法包含：

有效位信息取得步骤，由所述输入码中包含的信息求表示每个所述单位处理信息的有效比特的信息即有效位信息；

单位处理信息串取得步骤，由包含在所述输入码中的索引取得注册在词典部分中的单位处理信息的串；以及

结合步骤，使用所述有效位信息，将所述取得的一个或多个单位处理信息串中包含的一个或多个单位处理信息的有效比特结合的结果作为解码信号。

13.如权利要求12所述的信息解码方法，其特征在于，还具有：

分离步骤，将输入码分离为整数码和差分码；

整数形式信号解码步骤，将所述整数码解码后生成整数形式信号；

浮点化步骤，将所述整数形式信号变换为浮点形式信号；以及

合成步骤，将在所述浮点形式信号的尾数部分和所述结合步骤的输出合成的信号中置换了尾数部分的所述浮点形式信号作为解码信号，

所述有效位信息取得步骤和所述单位处理信息串取得步骤以所述差分码中包含的信息或索引作为处理对象。

14.如权利要求12所述的信息解码方法，其特征在于，还具有：

分离步骤，将输入码分离为商码、乘数码和差分码；

商解码步骤，将所述商码解码来求商信号；

乘数解码步骤，将所述乘数码解码来求乘数；

乘法步骤，对所述商信号乘以所述乘数；以及

加法步骤，将所述乘法步骤的输出和所述结合步骤的输出相加的结果作为解码信号，

所述有效位信息取得步骤和所述单位处理信息串取得步骤将所述差分码中包含的信息或索引作为处理对象。

15.如权利要求12所述的信息解码方法，其特征在于，还具有：

分离步骤，将输入码分离为整数码、乘数码和差分码；

整数信号解码步骤，将所述整数码解码来求整数信号；

乘数解码步骤，将所述乘数码解码来求乘数；以及

乘数判定步骤，判定所述乘数是否为1，

所述单位处理信息串取得步骤将差分码中包含的索引作为处理对象，

在所述乘数为1且所述整数信号不为0的情况下，

所述有效位信息取得步骤求所述整数信号的有效位数n作为有效位信息，

所述信息解码方法还具有输出将在所述结合步骤中得到的解码信号作为基于所述有效位信息的尾数部分的低位即输出信号的尾数部分的位数-n比特部分的浮点形式信号的步骤，

在所述乘数不为1且所述整数信号不为0的情况下，

所述信息解码方法还具有：

乘法步骤，对所述整数信号乘以所述乘数；以及

加法步骤，将所述乘法步骤的输出和在所述结合步骤中得到的解码信号相加的结果作为输出信号，

在所述整数信号为0的情况下，

所述信息解码方法还具有将浮点形式信号作为输出信号的步骤，所述浮点形式信号将在所述结合步骤中得到的解码信号作为尾数部分。

16.一种信息压缩编码装置，搜索与以一定比特数的处理单位表现的信息即单位处理信息的串对应的、注册在词典部分中的单位处理信息即词典信息的串，并对输入信息进行压缩编码，其特征在于，

所述信息压缩编码装置包括：

一致判定部分，将由所述输入信息生成的单位处理信息串中的与输入信息的有效位对应的有效比特与词典信息的对应的比特进行比较，如果所述有效比特和对应的比特全部一致，则判定所述单位处理信息和词典信息一致；

搜索部分，在能够判断为与由所述输入信息生成的单位处理信息的串一致的词典信息的串中，搜索最长的词典信息的串，并求该最长的词典信息的串的索引；以及

输出部分，输出所述索引。

17.如权利要求16所述的信息压缩编码装置，其特征在于，

输入信息为采样串，

所述信息压缩编码装置还具有单位处理信息生成部分，其对于每个采样，将构成采样中的有效位的比特组按每个所述处理单位进行分割，从而生成所述单位处理信息，

在所述单位处理信息生成部分中，在通过分割而剩余了采样的比特的情况下，或者采样的比特不满处理单位的情况下，对剩余的比特或不满处理单位的采样的比特追加虚比特而作为单位处理信息，并使得追加的虚比特部分不是有效的比特。

18.一种信息解码装置，对输入码进行解码而得到解码信息，该输入码包含词典部分的索引中的其中一个索引，该词典部分注册了以一定比特数的处理单位表现的信息即单位处理信息的串，其特征在于，该信息解码装置包含：

有效位信息取得部分，由所述输入码中包含的信息求表示每个所述单位处理信息的有效比特的信息即有效位信息；

单位处理信息串取得部分，由包含在所述输入码中的索引取得注册在词典部分中的单位处理信息的串；以及

结合部分，使用所述有效位信息，将所述取得的一个或多个单位处理信息串中包含的一个或多个单位处理信息的有效比特结合的结果作为解码信号。

19.如权利要求18所述的信息解码装置，其特征在于，还具有：

分离部分，将输入码分离为整数码和差分码；

整数形式信号解码部分，将所述整数码解码后生成整数形式信号；

浮点化部分，将所述整数形式信号变换为浮点形式信号；以及

合成部分，将在所述浮点形式信号的尾数部分和所述结合部分的输出合成的信号中置换了尾数部分的所述浮点形式信号作为解码信号，

所述有效位信息取得部分和所述单位处理信息串取得部分以所述差分码中包含的信息或索引作为处理对象。

20.如权利要求18所述的信息解码装置，其特征在于，还具有：

分离部分，将输入码分离为商码、乘数码和差分码；

商解码部分，将所述商码解码来求商信号；

乘数解码部分，将所述乘数码解码来求乘数；

乘法部分，对所述商信号乘以所述乘数；以及

加法部分，将所述乘法部分的输出和所述结合部分的输出相加的结果作为解码信号，

所述有效位信息取得部分和所述单位处理信息串取得部分将所述差分码中包含的信息或索引作为处理对象。

21.如权利要求16所述的信息压缩编码装置，其特征在于，具有：

多个散列表；以及

切换部分，在k字符的长度的单位处理信息被注册在词典中的情况下，将追加不一致字符时注册的词典的索引和不一致字符作为散列关键，注册在散列表中，

所述搜索部分对于一个词典注册改变最长一致字符的接着的1字符的有效位信息，根据有效位信息选择散列表而进行注册，在搜索时使用与有效位信息对应的散列表来进行搜索。

22.一种信息解码方法，对输入码进行解码而得到解码信息，该输入码包含词典部分的索引中的索引，该词典部分对应于索引注册了以一定比特数表现的单位处理信息的串或对应于串的信息，该信息解码方法包含：

有效位信息取得步骤，由所述输入码中包含的信息，取得表示每个所述单位处理信息的有效比特的有效位信息；

单位处理信息串取得步骤，由在词典部分中注册的单位处理信息的串或注册的对应于串的信息，取得对应于包含在所述输入码中的每个索引的单位处理信息的串；以及

掩码处理步骤，使用所述有效位信息确定所述取得的单位处理信息的串中的有效部分，从而得到解码信息。

23.一种信息解码方法，对输入码进行解码而得到解码信息，该输入码包含词典部分的索引中的索引，该词典部分对应于索引注册了以一定比特数表现的单位处理信息的串或对应于串的信息，该信息解码方法包含：

有效位信息取得步骤，由所述输入码中包含的信息，取得表示每个所述单位处理信息的有效比特的有效位信息；

单位处理信息串取得步骤，由在词典部分中注册的单位处理信息的串或注册的对应于串的信息，取得对应于包含在所述输入码中的每个索引的单位处理信息的串；以及

结合步骤，使用所述有效位信息，将所述取得的一个或多个单位处理信息的串中包含的一个或多个单位处理信息的有效比特结合，从而产生解码信号。

Images