Abstract:
An apparatus includes: a storage storing data input and sliding stored data per input; first and second comparators comparing in parallel the input data with each stored data and obtaining a position of data matching the input data; first and second determiners each determining whether a stored data matches the input data; a holder holding the result by the first or second comparator; a generator generating a value representing the position; a generator obtaining a longest length of a matching data list of the stored data that match the input data compared by the second comparator and that is at positions consecutive over each input, and generating a value representing the length; a generator generating a value using the input data as is; and a generator generating a code including these values. The comparison by the second comparator is controlled based on the result by the first or second comparator.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    The present application claims priority to and incorporates by reference the entire contents of Japanese Patent Application No. 2009-213802 filed in Japan on Sep. 15, 2009. 
       BACKGROUND OF THE INVENTION 
       [0002]    1. Field of the Invention 
         [0003]    The present invention relates to a data processing apparatus for and a data processing method of performing lossless compression encoding of data. 
         [0004]    2. Description of the Related Art 
         [0005]    Run length encoding (RLE) is one of data compression algorithms and classified as lossless compression. In the run length encoding, consecutive data are encoded by expressing a datum and a number of times the datum continues to compress the continuous data. 
         [0006]    For example, a data string “AAAAABBBBBBBBBAAA” is expressible as a data string “A5B9A3” after encoding. This means that “A” continues 5 times, “B” continues 9 times, and then “A” continues 3 times. In this example, a number of times that a datum continues is disposed behind the datum. Alternatively, the number of times that the datum continues may be disposed first and the number of that data may be disposed after the number. In the latter case, the data string of the encoded data is expressed as “5A9B3A.” 
         [0007]    In the above-described example, if it is determined beforehand that there are only two types of data, “A” and “B,” and that the datum “A” comes first, the above data string is expressible as only “593.” When following this rule, if the datum “B” is found first, it may be considered that the datum “A” continues zero time first. For example, a data string “BBBAAAABBBBBAAA” is expressible as “03553” after encoding. 
         [0008]    As a method of efficiently compressing data, a method of compressing by universal coding has been put into practical use. Universal coding is a lossless data compression method and is applicable to various types of data (for example, character code and object code) since a statistical nature of an information source is not presupposed beforehand upon data compression. 
         [0009]    A representative universal coding method is Ziv-Lempel coding. As Ziv-Lempel coding, two algorithms of a universal type and an incremental parsing type have been proposed. One practical method using the universal type algorithm is Lempel-Ziv-Storer-Syzmanski (LZSS) coding. Another practical method using the incremental parsing type algorithm is Lempel-Ziv-Welch (LZW) coding. 
         [0010]    In an encoding algorithm of LZ77 coding, which becomes the basis of LZSS coding, encoding data are divided into strings of a maximum length matching from an arbitrary position of a past data string and these are encoded as a duplicate of the past data string. 
         [0011]    More specifically, a moving window that stores encoded input data and a lookahead buffer that stores data to be encoded are provided, and a data string of the lookahead buffer is compared with all partial strings of a data string of the moving window to obtain a matching partial string of a maximum length in the moving window. In order to designate this partial string of the maximum length in the moving window, a set of “a start position of the partial string of the maximum length,” “a matching length,” and “a next symbol that yields a mismatch” is encoded. 
         [0012]    Next, the encoded data string in the lookahead buffer is moved to the moving window, and a new data string, which corresponds to the encoded data string, is input to the lookahead buffer. Thereafter, the same processing is repeated, so that data is decomposed into partial data strings and encoded. 
         [0013]    Generally, in LZSS coding, since it is necessary to detect a longest match with an input data string as many times as the number of the moving windows that store the encoded input data, it is said that an amount of computation is increased but a high compression ratio is achieved. 
         [0014]    Further, in an encoding algorithm of LZW coding, a rewritable dictionary is installed, input character strings are sorted into different character strings, and the character strings are designated with numbers in the order they appear and registered into the dictionary. Further, a currently input character string is represented by only a. dictionary number of a longest matching character string registered in the dictionary. Compared to LZSS coding, this LZW coding is lower in its compression ratio, but is simpler, easier in its computation, and higher speed processing is possible. Thus, it is widely used in file compression in a storage apparatus or in data transmission. 
         [0015]    In the above LZ77 coding, it takes the longest time in searching for the longest matching character string at the time of encoding. Thus, in order to speed up LZ77 coding, it is necessary to speed up the search for the longest matching character string. 
         [0016]    Japanese Patent No. 2713369 discloses a two-byte hash method, by a combination of a hash method and a linked list, of obtaining a matching position of two characters, comparing one character by one character for a match of three characters or more, and finally detecting a longest matching position. 
         [0017]    Further, as a technique of speeding up hardware processing, Japanese Patent No. 3610381 discloses a structure including an input first in first out (FIFO)  600 , a slide FIFO  601 , and a search circuit  602  that has as many comparators as the size of the slide as illustrated in  FIG. 15 . In this structure, the search circuit  602  compares plural data stored in the input FIFO  600  with plural past input data stored in the slide FIFO  601  in parallel and sequentially detects both a longest matching position and a matching length at the same time. 
         [0018]    Further, Japanese Patent No. 3730385 discloses a data compression apparatus having a comparator in a place where correlation is likely to occur (for example, directly above or left) in a limited manner, such that a hardware load when having as many comparators as the number of moving windows in parallel is reduced, and processing speed and hardware scale are taken into consideration. 
         [0019]    Moreover, Japanese Patent No. 4000266 proposes a method of performing a run length encoding on an index value matching the dictionary by performing Move to Front (MTF) control on a small dynamic dictionary. 
         [0020]    Furthermore, Japanese Patent No. 3922386 discloses a technique of obtaining a matching length by comparing plural data at once using a parallel comparing unit. 
         [0021]    However, in the above method of Japanese Patent No. 2713369 using the combination of the hash method and the linked list, a two-character 16-bit hash requires a hash table of about 64,000 words. This is effective for software but requires a large capacity for hardware. Consequently, when Japanese Patent No. 2713369 is implemented with small-scale hardware, for example a third character and characters thereafter are compared one character by one character, and thus processing takes time. 
         [0022]    Further, in Japanese Patent No. 4000266 performing MTF control using a small dictionary, if the number of words registered in the dictionary is small, for example, if one word is one byte and a depth of the dictionary is 64 words, even if there is a match, 8 bits are just converted to 6 bits. Accordingly, it is necessary to increase the number of words registered in the dictionary, but in that case, it becomes difficult for a match with the dictionary to occur. 
         [0023]    In Japanese Patent No. 4000266, in order to solve this, period detection is performed and the number of words of the dictionary is obtained through the period detection as illustrated in  FIG. 5 . To perform this period detection, a two-pass method or a pipeline-processing on period detection and on an encoding process using a work memory need to be used. 
         [0024]    In the two-pass method, processing is divided into two stages: a period detection process and an encoding process. The period detection process is first performed on data to be encoded, and then the encoding process is performed on the data to be encoded using the obtained period. Therefore, the processing takes extra time. Even in the method using the work memory, a large memory area for the pipeline processing of the period detection and the encoding processes is required. 
         [0025]    In Japanese Patent No. 3730385, the number of comparators is reducible since the comparators are provided only at places where correlation is likely to occur. However, because plural line memories need to be provided, the hardware scale increases. 
         [0026]    Furthermore, in Japanese Patent No. 3610381, the same number of circuits for obtaining a matching length as the number of slides need to be prepared as illustrated in  FIG. 9  of the Patent, and the same number of circuits for comparing data as the number of the input FIFOs need to be prepared as illustrated in  FIG. 10  of the Patent. Accordingly, a relatively small-scale structure having, for example, a slide length of 32 and 8 input FIFOs is easily implementable, but to increase the compression ratio, a slide length of, for example, 256 or more is required, increasing the scale. 
         [0027]    Further, in Japanese Patent No. 3610381, the input FIFO  11  or the slide FIFO must perform shifting of a plurality of data at once based on a matching length. If this process is implemented by hardware, the structure becomes complex. That is, the non-regular shift process or comparison process for the matching length makes the whole hardware complicated. Therefore, in the configuration of Japanese Patent No. 3610381, it is difficult to improve the compression ratio by increasing the number of slides. 
         [0028]    Further, in Japanese Patent No. 3610381, in order to obtain the longest matching position and length between the slide and the input data, two kinds of processes, a slide search and a list search, need to be performed. That is, the entire slide is first searched by the slide search, and thereafter the process is switched to the list search of searching from a plurality of matched lists based on the search result of the slide search. When the input data does not match the list, the longest matching length until that time is obtained, and the slide search starts again with that input data. 
         [0029]    As described above, in Japanese Patent No. 3610381, when the process is switched to the slide search as no match is obtained in the list search, clock encoding is not performed for a period of at least one clock, and this decreases the processing speed. 
         [0030]    Moreover, in Japanese Patent No. 3922386, the processing speed is increased by comparing a plurality of data at once using a matrix array  704  in which a history buffer composed of a latch  700  and a latch  701  and a comparing unit  703 , which compares the plurality of data input to an input buffer  702  in a direction perpendicular to the history buffer, are arranged in a matrix of a history buffer length and an input buffer length as illustrated in  FIG. 16 . 
         [0031]    However, in the method of Japanese Patent No. 3922386, the number of data processible at once is limited to the number of data determined by a configuration of the parallel comparing unit. In the example of  FIG. 16 , the number of data processible in parallel is limited to 12 according to the input byte length of the input buffer  702  of 12 bytes. The number of data processible at once may be increased by increasing the scale of the parallel comparing unit, but this increases the hardware scale and causes restrictions upon installing the hardware in, for example, an ASIC. 
       SUMMARY OF THE INVENTION 
       [0032]    It is an object of the present invention to at least partially solve the problems in the conventional technology. 
         [0033]    According to an aspect of the present invention, a data processing apparatus includes: a slide storage unit that sequentially stores input data input from a first terminal of the slide storage unit and sequentially slides stored data toward a second terminal of the slide storage unit upon each input; a first comparing unit that compares the input data input from the first terminal with each of the stored data in the slide storage unit in parallel and obtains a position of matching data of the stored data in the slide storage unit that matches the input data; a first determining unit that determines whether or not at least one of the stored data in the slide storage unit matches the input data compared by the first comparing unit based on a result of the comparison by the first comparing unit; a second comparing unit that compares the input data input from the first terminal with each of the stored data in the slide storage unit in parallel and obtains a position of matching data of the stored data in the slide storage unit that matches the input data; a second determining unit that determines whether or not at least one of the stored data in the slide storage unit matches the input data compared by the second comparing unit based on a result of the comparison by the second comparing unit; a holding unit that holds the result of the comparison by the first or second comparing unit based on results of the determinations by the first and the second determining units; an address value generating unit that generates an address value representing the position of the matching data based on the result of the comparison by the first or second comparing unit that is held by the holding unit according to the result of the determination by the second determining unit; a length value generating unit that obtains a longest length of a matching data list of the store data in the slide storage unit that match the input data compared by the second comparing unit and that is at positions in the slide storage unit consecutive over each input of the input data to the slide storage unit, and generates a length value representing the longest length, according to the result of the determination by the second determining unit; a data value generating unit that generates a data value that uses the input data as is according to the results of the determinations by the first and second determining units; and a code generating unit that generates a code including the address value, the length value, and the data value, wherein the comparison by the second comparing unit of comparing each of the stored data in the slide storage unit with the input data input from the first terminal is controlled based on the result of the comparison by the first or second comparing unit held in the holding unit. 
         [0034]    According to another aspect of the present invention, a data processing method includes: first comparing of comparing input data input from a first terminal of a slide storage unit that sequentially stores the input data and sequentially slides stored data toward a second terminal of the slide storage unit upon each input, with each of the stored data in the slide storage unit in parallel and obtaining a position of matching data in the slide storage unit that matches the input data; first determining of determining whether or not at least one of the stored data in the slide storage unit matches the input data compared in the first comparing based on a result of the comparison in the first comparing; second comparing of comparing the input data input from the first terminal of the slide storage unit with each of the stored data in the slide storage unit in parallel and obtaining a position of matching data in the slide storage unit that matches the input data; second determining of determining whether or not at least one of the stored data in the slide storage unit matches the input data compared in the second comparing based on a result of the comparison in the second comparing; holding the result of the comparison in the first or second comparing in a holding unit, based on results of the determinations in the first determining and the second determining; generating an address value representing the position of the matching data based on the result of the comparison by the first or second comparing held in the holding unit according to the result of the determination in the second determining; obtaining a longest length of a matching data list of the stored data in the slide storage unit that match the input data compared in the second comparing and that is at positions in the slide storage unit consecutive over each input of the input data to the slide storage unit, and generating a length value representing the longest length, according to the result of the determination in the second determining; generating a data value that uses the input data as is according to the results of the determinations in the first determining and the second determining; and generating a code including the address value, the length value, and the data value, wherein the comparing of each of the stored data in the slide storage unit with the input data input from the first terminal of the slide storage unit is controlled based on the result of the comparison in the first or second comparing held in the holding unit. 
         [0035]    The above and other objects, features, advantages and technical and industrial significance of this invention will be better understood by reading the following detailed description of presently preferred embodiments of the invention, when considered in connection with the accompanying drawings. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0036]      FIG. 1  is a block diagram illustrating an example of a configuration of a printer device to which a data processing apparatus according to the present invention is applicable; 
           [0037]      FIG. 2  is a block diagram illustrating an example of a configuration of an encoder; 
           [0038]      FIG. 3  illustrates an example of a code format; 
           [0039]      FIG. 4  illustrates an encoding process according to the present embodiment; 
           [0040]      FIG. 5A  illustrates a flag process in a slide search process and a list search process; 
           [0041]      FIG. 5B  illustrates a flag process in a slide search process and a list search process; 
           [0042]      FIG. 6A  illustrates a slide search process and a list search process when a flag process is performed; 
           [0043]      FIG. 6B  illustrates a slide search process and a list search process when a flag process is performed; 
           [0044]      FIG. 6C  illustrates a slide search process and a list search process when a flag process is performed; 
           [0045]      FIG. 6D  illustrates a slide search process and a list search process when a flag process is performed; 
           [0046]      FIG. 6E  illustrates a slide search process and a list search process when a flag process is performed; 
           [0047]      FIG. 6F  illustrates a slide search process and a list search process when a flag process is performed; 
           [0048]      FIG. 6G  illustrates a slide search process and a list search process when a flag process is performed; 
           [0049]      FIG. 6H  illustrates a slide search process and a list search process when a flag process is performed; 
           [0050]      FIG. 7  is an example of a flowchart illustrating an overall flow of an encoding process according to the present embodiment; 
           [0051]      FIG. 8  is a flowchart illustrating a slide search process in further detail; 
           [0052]      FIG. 9  is a flowchart illustrating a list search process in further detail; 
           [0053]      FIG. 10  is a flowchart illustrating a slide search process in further detail; 
           [0054]      FIG. 11  is a circuit diagram illustrating an example of a hardware configuration of a slide/list generation processing unit; 
           [0055]      FIG. 12  is a block diagram illustrating an example of a configuration of a decoder; 
           [0056]      FIG. 13  is an example of a flowchart illustrating a decoding process of a decoder; 
           [0057]      FIG. 14  is a circuit diagram illustrating an example of a hardware configuration of a slide expanding unit; 
           [0058]      FIG. 15  is a block diagram illustrating an example of a configuration of an encoding device according to a conventional technique; and 
           [0059]      FIG. 16  is a block diagram illustrating an example of a configuration of an encoding device according to a conventional technique. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0060]    Hereinafter, an embodiment of a data processing apparatus according to the present invention will be described in detail with reference to the accompanying drawings.  FIG. 1  illustrates an example of a configuration of a printer device  200  to which a data processing apparatus according to the present invention is applicable. In the example of  FIG. 1 , the printer device  200  includes a control unit  230 , a main memory  210 , a printer engine  211 , and a flash memory  240  that is a non-volatile memory. The flash memory  240  may be built in or removably attached to the printer device  200 . 
         [0061]    The control unit  230  includes a central processing unit (CPU)  212 , a CPU I/F  201 , a main memory arbiter  202 , a main memory controller  203 , an encoding unit  204 , a decoding unit  205 , a gradation processing unit  206 , an engine controller  207 , a flash memory controller  241 , an encoder  242 , and a decoder  243 . 
         [0062]    The CPU  212  controls an overall operation of the printer device  200  by a program stored in the main memory  210 . The CPU  212  is connected to the main memory arbiter  202  via the CPU I/F  201 . The main memory arbiter  202  arbitrates accesses by the CPU  212 , the encoding unit  204 , the decoding unit  205 , a communication controller  208 , the flash memory controller  241 , the encoder  242 , and the decoder  243  with respect to the main memory  210 . 
         [0063]    The main memory  210  is connected to the main memory arbiter  202  via the main memory controller  203 . The main memory controller  203  controls access to the main memory  210 . 
         [0064]    The main memory  210  has a program area  210 A, a page description language (PDL) data storage area  210 B, a CMYK band data storage area  210 C, a CMYK page code storage area  210 D, and another area or other areas  210 E. A program executed by the CPU  212  is stored in the program area  210 A. PDL data supplied from, for example a computer  220  is stored in the PDL data storage area  210 B. CMYK band data is stored in the CMYK band data storage area  210 C. Code data in which band data is compression-encoded is stored in the CMYK page code storage area  210 D. Data not described above are stored in the area  210 E. 
         [0065]    The encoding unit  204  encodes band data stored in the main memory  210 . The encoded band data is supplied to the main memory  210  via the main memory arbiter  202  and the main memory controller  203  and written in the CMYK page code storage area  210 D. The decoding unit  205  reads out encoding band data encoded by the encoding unit  204  and written in the main memory  210  from the main memory  210  and decodes the encoding band data in synchronization with the printer engine  211  which will be described later. The decoded band data is supplied to the gradation processing unit  206 . The gradation processing unit  206  performs a gradation process on the band data supplied from the decoding unit  205  and transmits the result of the gradation process to the engine controller  207 . 
         [0066]    The engine controller  207  controls the printer engine  211 . In  FIG. 1 , only one of CMYK blocks is illustrated as the printer engine  211 , and the other blocks are omitted for simplicity. 
         [0067]    The communication controller  208  controls communications performed via a network  221 . For example, PDL data output from the computer  220  is received by the communication controller  208  via the network. The communication controller  208  transmits the received PDL data to the main memory  210  through the main memory arbiter  202  and the main memory controller  203 . 
         [0068]    The network may be a type in which communications are performed within a predetermined range like a local area network (LAN) or a type in which communications are performed in a wider range like the Internet. The network is not limited to a wired communication network but may be of any type, for example, a wireless communication network or a serial communication according to such as universal serial bus (USB) or institute electrical and electronics engineers (IEEE) 1394. 
         [0069]    Programs operating on the CPU  212  and various data used by the corresponding programs are compression-encoded by a compression encoding scheme according to the present embodiment and stored in the flash memory  240 . For example, a program for implementing an additional function of the printer device  200  is compression-encoded and stored in the flash memory  240 . The present invention is not limited thereto, and a program for implementing a basic operation of the printer device  200  may be compression-encoded and stored in the flash memory  240 . The flash memory controller  241  controls access to the flash memory  240 . 
         [0070]    The encoder  242  performs compression encoding of data by a compression encoding scheme according to the present embodiment. The decoder  243  performs decoding on data compression-encoded by a corresponding compression encoding scheme. 
         [0071]    In such a configuration, for example, when the printer device  200  is powered ON and starts its operation, the flash memory controller  241  reads out compression-encoded data from the flash memory  240  according to an instruction of the CPU  212 . The compression-encoded data is, for example, one in which a program (program data) or various data is compression-encoded. The read-out compression data is supplied to the decoder  243  through the main memory arbiter  202 . 
         [0072]    The decoder  243  decodes the compression data to expand a compression code. Program data or various data in which the compression code is expanded is supplied to the main memory  210  through the main memory arbiter  202  and the main memory controller  203  and stored in the program area  210 A. 
         [0073]    For example, when the printer device  200  is powered OFF and finishes its operation, the main memory controller  203  reads out program data or various data from the main memory  210  according to an instruction by the CPU  212 . The read-out program data or various data are supplied to the encoder  242  through the main memory arbiter  202 . 
         [0074]    The encoder  242  compression-encodes the program data or various data using a compression encoding scheme according to the present embodiment. The compression-encoded compression data is supplied to the flash memory controller  241  through the main memory arbiter  202  and stored in the flash memory  240 . 
         [0075]    The flash memory  240  is slow in access rate compared to a dynamic random access memory (DRAM) used in the main memory  210 . For this reason, data to be stored in the, flash memory  240  is compression-encoded to reduce the data size, thereby compensating the slow access rate. 
         [0076]    An overall operation of the printer device  200  will be schematically described. For example, PDL data generated by the computer  220  is received by the communication controller  208  via the network  221  and stored in the PDL data storage area  210 B of the main memory  210 . The CPU  212  reads out the PDL data from the PDL data storage area  210 B, interprets the PDL data, and draws a CMYK band image based on the interpretation result. CMYK band data of the drawn CMYK band image is stored in the CMYK band data storage area  210 C of the main memory  210 . 
         [0077]    The encoding unit  204  reads out the CMYK band data from the CMYK band data storage area  210 C and encodes the CMYK band data, for example, using a predictive coding scheme. A code data in which the CMYK band data is encoded is stored in the CMYK page code storage area  210 D of the main memory  210 . 
         [0078]    The decoding unit  205  reads out the code data, which is the CMYK band data that has been encoded from the CMYK page code storage area  210 D, decodes the code data, and supplies the decoded CMYK band data to the gradation processing unit  206 . The gradation processing unit  206  performs a gradation process on the CMYK band data supplied from the encoding unit  205 . The gradation-processed CMYK band data is supplied to the printer engine  211  through the engine controller  207 . The printer engine  211  performs a print-out based on the CMYK band data. 
         [0079]    &lt;Encoder&gt; 
         [0080]      FIG. 2  illustrates an example of a configuration of the encoder  242 . In the encoder  242 , a data reading unit  300  reads outs program data or various data (hereinafter, referred to collectively as “data”) from the program area  210 A of the main memory  210  through the main memory controller  203  and the main memory arbiter  202 . The data read by the data reading unit  300  is supplied to a slide/list generation processing unit  301 . 
         [0081]    The slide/list generation processing unit  301  includes a slide storage unit of a FIFO type that sequentially stores input data. The slide/list generation processing unit  301  sequentially compares received data with past input data stored in the slide storage unit. When the received data is matched with the past input data, the slide/list generation processing unit  301  holds an address value “Address” representing a position of the corresponding past input data in the slide storage unit and counts up a length “Length” as a value representing a matching length. However, when the received data does not match the past input data, the slide/list generation processing unit  301  encodes a data value into a PASS code. The slide/list generation processing unit  301  outputs the PASS code, the address value “Address”, the length “Length”, and a matching flag FLAG representing whether or not the received data matches the past input data. 
         [0082]    The values output from the slide/list generation processing unit  301  are supplied to a code format generation processing unit  302 . The code format generation processing unit  302  encodes the PASS code, the address value “Address,” the length “Length,” and the matching flag FLAG in a format illustrated in  FIG. 3 . 
         [0083]    In  FIG. 3 , the PASS code has a header composed of a matching flag FLAG having a data length of one bit and a value of “0.” A data value having a data length of eight bits is connected after the header. A slide code has a header composed of a matching flag FLAG having a data length of one bit and a value of “1.” A length “Length” and an address “Address” that have a data length of eight bits, respectively, are sequentially connected after the header. The code format illustrated in  FIG. 3  is an example, and the present invention is not limited thereto. 
         [0084]    The PASS code and the slide code generated by the code format generation processing unit  302  are supplied to a code writing unit  303 . The code writing unit  303  writes the PASS code and the slide code in the flash memory  240  through the main memory arbiter  202  and the flash memory controller  241 . 
         [0085]    &lt;Overview of an Encoding Process&gt; 
         [0086]    Next, an encoding process in the slide/list generation processing unit  301  according to the present embodiment will be described. In the present embodiment, data encoding is performed by repeating a slide search process and a list search process. In the slide search process, past input data, stored in the slide storage unit, having a length of a predetermined unit matched with input data of one unit (for example, one byte) is searched. If data matching input data is not found in the past input data in the slide storage unit, the input data, as is, is used as the PASS code. 
         [0087]    In the slide search process, if past input data in the slide storage unit matching the input data is found, the list search process is performed using the matched past input data as a root. In the list search process, a past input data string (called a list) in the slide storage unit matching an input data string continuously input after the root input data is searched. 
         [0088]    In the list search process, when a list matching input data is no longer present, one of the previous lists just before that is selected and a position in the slide storage unit of the past input data that is the root of the selected list is output as the address value “Address,” and a length of that list is output as the length “Length.” 
         [0089]    That is, the slide/list generation processing unit  301  generates past input data that becomes a root of the list search process in the slide search process. Further, the slide/list generation processing unit  301  performs growth and selection of lists based on the root and then performs encoding based on a finally remaining list. 
         [0090]    A further detailed description will be given with reference to  FIG. 4 . In an example of  FIG. 4 , the slide storage unit includes 16 registers which are connected in series as designated by # 0  to # 15  and has a FIFO configuration. Each register is configured to store data of one unit (for example, one byte). Hereinafter, a register included in the slide storage unit is referred to as “slide.” 
         [0091]    In a process # 1 , 16 past input data “a, b, c, a, a, b, c, a, b, c, d, b, c, a, c, a” have been already input in the slides of the slide storage unit, respectively, in an order in which an input is new, that is, from the right-hand side to the left-hand side in  FIG. 4 . First, input data “a” is input to the slide/list generation processing unit  301 . In the slide search process, the input data “a” is compared with each of the past input data stored in the slides to search for matching data. In the example of  FIG. 4 , data stored in the slides # 0 , # 3 , # 4 , # 7 , # 13 , and # 15  match the input data. Therefore, data stored in the slides having these numbers become roots in the list search process. 
         [0092]    Since data matching the input data “a” is found from the past input data stored in the slides by the slide search process, a list search process of a process # 2  is performed. 
         [0093]    In the process # 2 , the past input data stored in each of the slides are slid to the left by one, and the input data “a” input in the process # 1  is added to the slide # 0  of the slide storage unit. Further, next input data “ input to the slide/list generation processing unit  301 . In the list search process, of the past input data stored in each of the slides, data matching the new input data “c” is searched from each of the slides in which the past input data that matched the input data were stored in the previous process # 1  just before the process # 2 . 
         [0094]    In the example of  FIG. 4 , the past input data stored in the slides # 0  and # 4  that matched the input data in the process # 1  do not match the input data in the process # 2 . The past input data stored in the slides # 3 , # 7 , # 13 , and # 15  that matched the input data in the process # 1  is data “c” and thus matches the new input data “c.” 
         [0095]    Since data matching the input data “c” in the process # 2  are found by the list search process of the process # 2  from each of the slides which store the past input data that matched the input data in the previous process # 1  just before the process # 2 , the next process is a list search process. Since the process # 2  is a starting point of the list search process, the length “Length” representing a list length has a value of “0.” 
         [0096]    In the process # 3 , similarly to the above-describe process # 2 , the past input data stored in each of the slides is slid by one, and the input data “c” input in the process # 2  is added to the slide # 0  of the slide storage unit. Further, next input data “b” is input to the slide/list generation processing unit  301 . Of the past input data stored in each of the slides, data matching the new input data “b” is searched from each of the slides in which the past input data that matched the new input data were stored in the previous process # 2  immediately before the process # 3 . 
         [0097]    In the example of  FIG. 4 , the past input data stored in the slide # 15  searched in the process # 2  does not match the input data in the process # 3 . The past input data in the process # 3  stored in the slides # 3 , # 7 , and # 13  searched in the process # 2  are data “b” and thus match the new input data “b.” In a next process # 4 , the past input data stored in the slides # 3 , # 7 , and # 13  become a list search target. That is, in the process # 3 , lists relative to the slides # 3 , # 7 , and # 13  remain. In the process # 3 , a list length is “1,” and thus the length “Length” has a value of “1.” 
         [0098]    The above-described processes are repeated to obtain a data string with a longest list. In the example of  FIG. 4 , in a process # 5 , past input data “c” stored in the slide # 13  list-searched in the previous process # 4  just before the process # 5  does not match new input data “g,” and thus the list is broken. In the process # 5 , one of the lists remaining in the previous process # 4  just before the process # 5  is selected and encoding into a slide code is performed with a position (number) of that slide in the slide storage unit being the address value “Address”, and a length of the list being the length “Length”. In the example of  FIG. 4 , the address value “Address” is “13,” and the length “Length” is “3.” 
         [0099]    In the process # 5 , the slide search process is performed on input data “g.” In this example, since data “g” is not stored as the past input data in any of the slide, there is no matching data. In this case, the process proceeds to a process # 6 , and the input data “g” is used “as is” to be encoded into a PASS code. 
         [0100]    When encoding into the PASS code is performed, in the process # 7 , past input data stored in each of the slides is slid by one, and the input data “g” input in the previous list search process (the process # 5 ) is added to the slide # 0  of the slide storage unit. The slide search process is performed on next input data “b.” 
         [0101]    The slide storage unit is able to slide the data stored in each slide by the FIFO method and thus to proceed to processing of next input data while maintaining the list for which matching with input data has been stored “as is.” 
         [0102]    For example, in the example of  FIG. 4 , in the process # 1 , the input data matches the past input data stored in the slides # 0 , # 3 , # 4 , # 7 , # 13 , and # 15 . By sequentially sliding the data stored in each of the slides as new data is input, next data is stored in the slides # 0 , # 3 , # 4 , # 7 , # 13 , and # 15  in the process # 2 . Therefore, in the slide storage unit, the data stored in the slide having the number which was found to match in the slide search process is compared with the input data in each list search process, whereby a data string of the past input data matching a data string of the input data is searchable. 
         [0103]    Since the slide storage unit employs the FIFO method as described above, the list search process is able to be easily performed. 
         [0104]    Further, according to the above-described process, if there is no list matching the input data in the list search process and the process proceeds from the list search process to the slide search process, a time period is generated during which encoding does not progress and which is worth one process. That is, when one process is to be performed in one clock, one clock is wasted when shifting from the list search process to the slide search process. 
         [0105]    &lt;Flag Process&gt; 
         [0106]    The slide search process and the list search process are controlled by a flag. A flag process in the slide search process and the list search process will be described with reference to  FIGS. 5A and 5B . 
         [0107]      FIG. 5A  illustrates an R flag RFLGm representing a result of the slide search process. As illustrated in  FIG. 5A , when input data “a” is input in a state in which past input data “a, b, c, a, a, b, c, a, b, c, d, b, c, a, c, a” are stored in the slides of the slide storage unit from right to left in the drawing, the past input data stored in the slides # 0 , # 3 , # 4 , # 13 , and # 15  match the input data. Therefore, R flags RFLG 0 , RFLG 3 , RFLG 4 , RFLG 7 , RFLG 13 , and RFLG 15 , which correspond to the slides having these numbers, are set to a value of “1” representing a match, respectively. 
         [0108]    When input data matches the past input data stored in the slides, the list search process is performed instead of an encoding process. At this time, a position of the R flag RFLGm relative to each slide is fixed. When the past input data stored in the slides do not match the input data, the input data is used “as is” to be encoded into a PASS code, and the slide search process is performed on next input data. 
         [0109]      FIG. 5B  illustrates an example of a W flag WFLGm representing a result of the list search process. In the list search process, data matching input data newly input is searched from the data stored in the slides for which the R flag RFLGm has been set to “1” of the slides. If matching data is found, a value of the W flag WFLGm for the corresponding slide is set to a value of “1” representing a match. 
         [0110]    In the example of  FIG. 5B , the list search process is performed on the data stored in the slides # 0 , # 3 , # 4 , # 7 , # 13 , and # 15  for which each value of the R flag RFLGm has been set to “1” of the past input data stored in the slides. Since the data stored in the slides # 3 , # 7 , # 13 , and # 15  match input data “c,” values of corresponding W flags WFLG 3 , WFLG 7 , WFLG 13  and WFLG 15  are set to a value “1” representing a match. Of the past input data stored in each of the slides, the data stored in the slides for which the value of the W flag WFLGm has been set to “1” indicate that the past input data stored in the slides matching the previously input data input immediately before is strung with the past input data matching the presently input data. 
         [0111]    Next, the W flag WFLGm having a value of “1” is searched. When the W flag WFLGm having a value of “1” is present, the list search process is performed on next input data in the same manner as described above using each W flag WFLGm as a new R flag RFLGm. 
         [0112]    If the W flag WFLGm having a value of “1” is not present as a result of the search, it means that the list has come to an end. In this case, one R flag RFLGm having a value of “1” is selected. An address value “Address” of the slide corresponding to the selected R flag RFLGm and the length “Length” at that time are encoded into the slide code. 
         [0113]    Next, the slide search process and the list search process when the R flag RFLGm and the W flag WFLGm are used will be described with reference to  FIGS. 6A to 6H . In  FIGS. 6A to 6H , similarly to  FIG. 4 , the slide storage unit has 16 slides designated by # 0  to # 15 . Further, let us assume that 16 past input data “a, b, c, a, a, b, c, a, b, c, d, b, c, a, c, a” are previously stored in the slides, in an order of newness, that is, in an ascending order of slide numbers. 
         [0114]    In the present embodiment, encoding is performed by repetitively performing the slide search process and the list search process. First, input data “a” is input, and the slide search process is performed ( FIG. 6A ). Data matching the input data “a” is searched from the slides of the slide storage unit. When data matching the input data is not found from the slides, corresponding input data is used “as is” to be encoded into a PASS code. 
         [0115]    When a slide storing data matching the input data is found, the value of the R flag RFLGm corresponding to the slide is set to “1,” and values of the other R flags RFLGm are set to “0.” In the example of  FIG. 6A , the data stored in the slides # 0 , # 3 , # 4 , # 7 , # 13 , and # 15  match the input data. In the slide search process, the data matching the input data is used as the root for list generation in the next list search process. 
         [0116]    Next, the storage contents of each of the slides are slid to the left, and the previous input data “a” immediately before is added to the slide # 0 . When a slide storing the data matching the input data is found in the slide search process as described above, the process proceeds to the list search process ( FIG. 6B ) instead of the encoding process, and the value of the length “length” is set to “0.” The values of the R flags RFLGm (R flags RFLG 0 , RFLG 3 , RFLG 4 , RFLG 7 , RFLG 13 , and RFLG 15 ) corresponding to the slides (the slides # 0 , # 3 , # 4 , # 7 , # 13 , and # 15 ) storing the data matching the input data are set to “1,” and the values of the other flags RFLGm are set to “0.” 
         [0117]    Next, input data “c” is input. In the list search process, of the slides each for which the value of the corresponding R flag RFLGm is “1,” a slide storing the data matching the input data “c” is searched. In the example of  FIG. 6B , of the slides each for which the value of the R flag RFLGm is “1,” the data stored in the slides # 3 , # 7 , # 13 , and # 15  match the input data. The slides # 0  and # 4  are excluded. The values of the W flag WFLGm (the W flags WFLG 3 , WFLG 7 , WFLG 13 , and WFLG 15 ) corresponding to these slides storing the data matching the input data are set to “1,” and the values of the other W flags WFLGm are set to “0.” 
         [0118]    Next, the storage contents of each of the slides are slid to the left, and the previous input data “c” immediately before is added to the slide # 0 . The process proceeds to the next list search process ( FIG. 6C ) instead of the encoding process, and the value of the length “length” is set to “1.” The values of the W flags WFLGm are set to the R flags RFLGm to update the R flags RFLGm. 
         [0119]    Next, input data “b” is input. In the list search process, of the slides each for which the value of the corresponding R flag RFLGm is “1,” a slide storing the data matching the input data “b” is searched. In the example of  FIG. 6C , of the slides each for which the value of the R flag RFLGm is “1,” the data stored in the slides # 3 , # 7 , and # 13  match the input data. The slide # 15  is excluded. The values of the W flag WFLGm (the W flags WFLG 3 , WFLG 7 , and WFLG 13 ) corresponding to the slides storing the data matching the input data are set to “1,” and the values of the other W flags WFLGm are set to “0.” 
         [0120]    Next, the storage contents of each of the slides are slid to the left, and the previous input data “b” immediately before is added to the slide # 0 . The process proceeds to the next list search process ( FIG. 6D ) instead of performing the encoding process, and the value of the length “length” is set to “2.” The values of the W flags WFLGm are set to the R flags RFLGm to update the R flags RFLGm. 
         [0121]    Next, input data “d” is input. In the list search process, of the slides each for which the value of the corresponding R flag RFLGm is “1,” a slide storing the data matching the input data “d” is searched. In the example of  FIG. 6D , the data stored in the slide # 13  matches the input data. Meanwhile, the slides # 3  and # 7  are excluded. The value of the W flag WFLG 13  corresponding to the slide storing the data matching the input data is set to “1.” 
         [0122]    Next, the storage contents of each of the slides are slid to the left, and the previous input data “d” input immediately before is added to the slide # 0 . The process proceeds to the next list search process ( FIG. 6E ) without performing the encoding process, and the value of the length “length” is set to “3.” The values of the W flags WFLGm are set to the R flags RFLGm to update the R flags RFLGm. 
         [0123]    Next, input data “a” is input. In the list search process, of the slides each for which the value of the corresponding R flag RFLGm is “1,” a slide storing the data matching the input data “a” is searched. In the example of  FIG. 6E , the slide # 13  is excluded, and thus the slide storing the data matching the input data “a” is not present. That is, a continuing list is not present. Accordingly, a position of the slide for which the value of the R flag RFLGm is “1” in the slide storage unit (a position of the slide # 13  in the example of  FIG. 6E ) is the address value “Address,” the value of the length “Length” is “3,” and the value of the matching flag FLAG is “1.” These values are encoded into a slide code as illustrated in  FIG. 3 . All of the values of the W flags WFLG are now set to “0,” and the process proceeds to the slide search process ( FIG. 6F ). 
         [0124]    A slide search after the breakage of the list is performed on the input data “a” in the previous list search process performed immediately before ( FIG. 6F ). Data matching the input data “a” is searched from the slides of the slide storage unit. If data matching the input data is not found from any of the slides, the corresponding input data is used “as is” to be encoded into a PASS code. 
         [0125]    When the slide storing data matching the input data is found, the value of the R flag RFLGm corresponding to the slide is set to “1.” In the example of  FIG. 6F , the data stored in the slides # 3 , # 4 , # 7 , # 8 , and # 11  match the input data. In the slide search process, the data that matched the input data are used as the roots for list generation in the next list search process. 
         [0126]    Next, the storage contents of each of the slides are slid to the left, and input data “a” is added to the slide # 0 . When the slide storing data matching the input data is found in the slide search process as described above, the process proceeds to the list search process ( FIG. 6G ) without performing the encoding process, and the value of the length “length” is set to “0.” The values of the R flags RFLGm (R flags RFLG 3 , RFLG 4 , RFLG 7 , RFLG 8 , and RFLG 11 ) corresponding to the slides (the slides having the numbers # 3 , # 4 , # 7 , # 8 , and # 11 ) storing the data matching the input data are set to “1,” and the values of the other flags RFLGm are set to “0.” 
         [0127]    Next, input data “f” is input. In the list search process, of the slides each for which the value of the corresponding R flag RFLGm is “1,” a slide storing data matching the input data “f” is searched. In the example of  FIG. 6G , the slide storing the data matching the input data “f” is not present. At this point in time, since the value of the length “Length” is “0,” all of the values of the W flags WFLGm are set to “0,” and the process proceeds to the slide search process ( FIG. 6H ). 
         [0128]    The slide search process is performed on the input data “f” input in the previous list search process immediately before ( FIG. 6H ). Data matching the input data “f” is searched from the slides of the slide storage unit. In the example of  FIG. 6H , since the data matching the input data is not found from any of the slides, the corresponding input data is used “as is” to be encoded into a PASS code. Further, all of the values of the R flags RFLGm are set to “0.” 
         [0129]    The storage contents of each of the slides are slid to the left, and input data “f” is added to the slide # 0 , and the process proceeds to the next list search process. 
         [0130]    &lt;Details of an Encoding Process&gt; 
         [0131]    Next, an encoding process in the slide/list generation processing unit  301  will be described in further detail.  FIG. 7  is a flowchart illustrating an example of an overall flow of an encoding process according to the present embodiment. Before the process of the flowchart of  FIG. 7 , the code reading unit  300  already holds data of a certain length as process target data. 
         [0132]    In step S 10 , the slide/list generation processing unit  301  initializes a flag ListFLG, which indicates which of the slide search process and the list search process is effective, to a value “0”, which indicates that the slide search process is being performed. Next, in step S 11 , the slide/list generation processing unit  301  reads data of one unit from the code reading unit  300  as input data. The read input data is stored in the slide storage unit. 
         [0133]    When the input data is stored in the slide storage unit, in step S 12 , the slide search process is performed on the data of one unit, and in step S 13 , the list search process is performed on the data of one unit. As will be described later in further detail, in the present embodiment, a slide search unit that performs the slide search process and a list search unit that performs the list search process are separately configured, and thus the processes of step S 12  and step S 13  are able to be performed in parallel. 
         [0134]    The process proceeds to step S 14 , and the slide/list generation processing unit  301  determines whether or not the value of the flag ListFLG is “0.” When it is determined to be “0,” the slide search process is presently effective, and the process proceeds to step S 15 . In step S 15 , it is determined whether or not a value of a flag SFINDFLG is “1.” When it is “1,” it is determined that past input data matching the input data was found in a slide storage unit  101 , and thus in step S 16 , the value of the flag ListFLG is set to “1” representing that the list search process is effective. 
         [0135]    Then, the process proceeds to step S 25 , and the input data is added to the slide storage unit. In step S 26 , it is determined whether or not processing on all of process target data has been completed. When it is determined as not completed, the process returns to step S 11 , and next data of one unit is read in as input data. However, when it is determined as completed, the series of encoding processes are ended. 
         [0136]    Meanwhile, when it is determined in step S 15  that the value of the flag SFINDFLG is “0,” it is determined that past input data matching the input data was not found in the slide storage unit  101 , and the process proceeds to step S 17 . In step S 17 , the value of the flag ListFLG is set to “0,” to set the slide search process as effective. In step S 18 , the input data is encoded into the PASS code. Further, the value of the matching flag FLAG is set to “0,” and the process proceeds to step S 25 . 
         [0137]    When it is determined in step S 14  that the value of the flag ListFLG is not “0” but “1,” it is determined that the list search process is presently effective, and the process proceeds to step S 19 . In step S 19 , it is determined whether or not the value of the flag LFINDFLG is “1.” When it is determined to be “1,” the process proceeds to step S 25 . 
         [0138]    Meanwhile, when it is determined in step S 19  that the value of the flag LFINDFLG is not “1,” that is, the value of the flag LFINDFLG is “0,” the process proceeds to step S 20 . In step S 20 , the address value “Address,” the length “Length”, and the matching flag FLAG are encoded into the slide code as illustrated in  FIG. 3 . The process proceeds to step S 21 , and it is determined whether or not the value of the flag SFINDFLG is “1.” When it is determined to be “1,” it is determined that the list has continued in the list search process, and the process proceeds to step S 22 . The value of the flag ListFLG is set to “1,” and the process proceeds to step S 25 . 
         [0139]    When it is determined in step S 21  that the value of the flag SFINDFLG is “0,” it is determined that the list has broken in the list search process, and the process proceeds to step S 23 . The value of the flag ListFLG is set to “0.” In step S 24 , the input data is encoded into a PASS code “as is” and stored in a register  141 . The process proceeds to step S 25 . 
         [0140]      FIG. 8  is a flowchart illustrating an example of the slide search process in step S 12  of  FIG. 12  in further detail. In  FIGS. 8 ,  9 , and  10 , the slides in the slide storage unit are each represented as slide [x] to include the slide number. Further, a head slide in the slide storage unit having a FIFO configuration is designated as slide [ 0 ]. 
         [0141]    First, in step S 30  to step S 32 , the length “Length”, the flag SFINDFLG, and a variable IW are each initialized to a value of “0”. The process proceeds to step S 33 , and it is determined whether or not input data matches the past input data stored in a slide [IW]. When it is determined to match, the process proceeds to step S 34 , and the value of the flag SFINDFLG is set to “1,” and in step S 35 , the value of the R flag RFLG[IW] is set to “1.” 
         [0142]    Then, the process proceeds to step S 37 , and it is determined whether or not the variable IW is less than the slide size, that is, the number of slides included in the slide storage unit. When it is determined that the variable IW is less than the slide size, in step S 38 , “1” is added to the variable IW, and the process returns to step S 33 . When it is determined that the variable IW is equal to or greater than the slide size, a series of processes are ended. 
         [0143]    Meanwhile, when it is determined in step S 33  that the input data does not match the past input data stored in the slide [IW], the process proceeds to step S 36 , and the value of the R flag RFLG[IW] is set to “0.” Then, the process proceeds to step S 37 . 
         [0144]      FIG. 9  is a flowchart illustrating an example of the list search process in step S 13  of  FIG. 7  in further detail. First, in step S 40  and step S 41 , the flag LFINDFLG and the variable IW are each initialized to a value “0”. 
         [0145]    In step S 42 , it is determined whether or not input data is matches the past input data stored in the slide [IW] and the value of the R flag RFLG[IW] is “1.” When it is determined that these two conditions are satisfied, the process proceeds to step S 43 , and the value of the W flag WFLG[IW] is set to “1.” In step S 44 , the value of the flag LFINDFLG is set to “1.” Then, the process proceeds to step S 46 . 
         [0146]    Meanwhile, in step S 42 , when it is determined that the above-described condition is not satisfied, that is, the input data is not matched with the past input data stored in the slide [IW] and/or the value of the R flag RFLG[IW] is not “1,” the process proceeds to step S 45 , and the value of the W flag WFLG[IW] is set to “0”. Then, the process proceeds to step S 46 . 
         [0147]    In step S 46 , it is determined whether or not the variable IW is less than the slide size. When it is determined that the variable IW is less than the slide size, in step S 47 , “1” is added to the variable IW, and the process returns to step S 42 . Meanwhile, when it is determined that the variable IW is equal to or more than the slide size, the process proceeds to step S 48 . 
         [0148]    In step S 48 , it is determined whether or not the value of the flag LFINDFLG is “0.” When it is determined that the value is “0,” the process proceeds to step S 49 , and the variable IW is initialized to a value of “0.” In step S 50 , it is determined whether or not the value of the R flag RFLG[IW] is “1.” When it is determined to b “1,” the process proceeds to step S 51 . 
         [0149]    In step S 51 , the variable IW is set to the address value “Address,” and in step S 52 , the slide size is assigned to the variable IW. Then, the process proceeds to step S 53 . In step S 53 , it is determined whether or not the variable IW is less than the slide size. When it is determined that the variable IW is less than the slide size, in step S 54 , “1” is added to the variable IW, and the process returns to step S 50 . 
         [0150]    When it is determined in step S 53  that the variable IW is equal to or greater than the slide size, a series of processes are ended. For example, when the process proceeds to step S 53  via step S 52 , since in step S 52 , the slide size has been substituted into the variable IW, the process is inevitably finished. 
         [0151]    When it is determined in step S 48  that the value of the flag LFINDFLG is not “0,” the process proceeds to step S 55 , and the variable IW is initialized to a value of “0.” In step S 56 , the W flag WFLG[IW] is set with respect to the R flag RFLG[IW]. In step S 57 , it is determined whether or not the variable IW is less than the slide size. When it is determined that the variable IW is less than the slide size, in step S 5 B, “1” is added to the variable IW, and the process returns to step S 56 . Meanwhile, when it is determined in step S 57  that the variable IW is equal to or greater than the slide size, the process proceeds to step S 59 , and “1” is added to the length “Length.” Then, a series of processes are ended. 
         [0152]      FIG. 10  is a flowchart illustrating an example of a slide adding process in step S 25  of  FIG. 7  in further detail. First, in step S 70 , a value obtained by subtracting “1” from the number of slides is set to the variable IW. In step S 71 , the value of the slide [IW- 1 ] is stored in the slide [IW]. In step S 72 , it is determined whether or not the variable IW exceeds “0.” When it is determined that the variable IW exceeds “0,” the process proceeds to step S 73 , and “1” is subtracted from the variable IW. Then, the process returns to step S 71 . Meanwhile, when it is determined in step S 72  that the variable IW is less than “0,” the process proceeds to step S 74 , and input data is stored in the slide [ 0 ]. 
       A Hardware Configuration Example of the Slide/List Generation Processing Unit 
       [0153]      FIG. 11  illustrates an example of a hardware configuration of the slide/list generation processing unit  301  that performs the slide search process, the list search process, and the encoding process which are described above. The slide/list generation processing unit  301  includes a slide search unit  100 , the slide storage unit  101 , a list search unit  102 , and a controller  103 . 
         [0154]    The controller  103  includes, for example, a microprocessor and performs the processes of step S 11  to step S 26 , excluding step S 12  and step S 13 , described with reference to the flowchart of  FIG. 7  to control an operation of the slide/list generation processing unit  301 . For example, the controller  103  performs operation control based on the flag ListFLG representing which of the present slide search process and the list search process is effective. 
         [0155]    For example, input data of one unit is input per clock to the slide/list generation processing unit  301  and supplied to each of the slide search unit  100 , the slide storage unit  101 , and the list search unit  102 . The input data is also stored in the register  141  at an output side. The input data stored in the register  141  is used as a data value for the encoding of the PASS code. Hereinafter, one byte is used as one unit of data. 
         [0156]    The slide storage unit  101  includes n (for example, 256) slides  120   1 ,  120   2 , . . . , and  120   n , which are connected in series. Each slide includes a register and stores data of one unit. An output of each of the slides  120   1 ,  120   2 , . . . , and  120   n  is supplied to a next register and also supplied to one of input terminals of a comparator  111   m  of the slide search unit  100  which will be described later and one of input terminals of a comparator  130   m  of the list search unit  102 , respectively. 
         [0157]    In the slide code described in  FIG. 3 , the data lengths of the address value “Address” and the length “Length” depend on the number (n) of slides included in the slide storage unit  101 . That is, when the number (n) of slides is 256, the data lengths of the address value “Address” and the length “Length” are determined as having 8 bits, respectively, in order to be able to express a value of up to “256.” 
         [0158]    In the slide storage unit  101 , a FIFO configuration is formed with the n slides  120   1 ,  120   2 , . . . , and  120   n , and input data is sequentially transmitted from the slide  120   1  to the slide  120   2 , then to the slide  120   3 , . . . , and the to the  120   n  per one clock. 
         [0159]    The slide search unit  100  includes n comparators  111   1 ,  111   2 , . . . , and  111 , and a logical sum circuit  110  having n inputs. Each of the n comparators  111   1 ,  111   2 , . . . , and  111   n  compares data input to one of the input terminal with data input to the other one of the input terminals and outputs “1” when the two match and “0” when the two do not match. 
         [0160]    The outputs of the slides  120   1 ,  120   2 , . . . , and  120   n  included in the slide storage unit  101  are input to one of the input terminals of the comparators  111   1 ,  111   2 , . . . , and  111   n , respectively. Further, input data is input to the other one of the input terminals of the comparators  111   1 ,  111   2 , . . . , and  111   n . 
         [0161]    The outputs of the comparators  111   1 ,  111   2 , . . . , and  111   n  are input to the logical sum circuit  110  having the n inputs, respectively, and also input to selectors (SEL)  131   1 ,  131   2 , . . . ,  131   n  of the list search unit  102  which will be described later, respectively. An output of the logical sum circuit  110  is supplied to the controller  103  as the flag SFINDFLG. The flag SFINDFLG represents whether or not at least one of data in the slides  120   1 ,  120   2 , . . . , and  120   n  matches the input data. 
         [0162]    The list search unit  102  includes n comparators  130   1 ,  130   2 , . . . ,  130   n , n selectors  131   1 ,  131   2 , . . . ,  131   n , n registers  132   1 ,  132   2 , . . . ,  132   n , an address value generating unit  133 , and a logical sum circuit  18  having n inputs. Each of the n comparators  130   1 ,  130   2 , . . . , and  130   n  compares data input to one input terminal with data input to the other input terminal and outputs “1” when the two match and “0” when the two do not match. 
         [0163]    The outputs of the slides  120   1 ,  120   2 , . . . , and  120   n  included in the slide storage unit  101  are input to the one input terminals of the comparators  130   1 ,  130   2 , . . . , and  130   n , respectively. Further, input data is input to the other input terminals of the comparators  130   1 ,  130   2 , . . . , and  130   n . 
         [0164]    The outputs of the comparators  130   1 ,  130   2 , . . . , and  130   n  are input to the logical sum circuit  18  having the n inputs as the W flag WFLGm and also input to the other input terminals of the selectors  131   1 ,  131   2 , . . . ,  131   n , respectively. An output of the logical sum circuit  18  is supplied to the controller  103  as the flag LFINDFLG. The flag LFINDFLG represents that at least one of the flags WFLG 1 , WFLG 2 , . . . , WFLGn has a value of “1.” 
         [0165]    The outputs of the selectors  131   1 ,  131   2 , . . . , and  131   n  are stored in the registers  132   1 ,  132   2 , . . . , and  132   n , respectively, as the R flag RFLGm. The selectors  131   1 ,  131   2 , . . . , and  131   n  are controlled by the flag ListFLG supplied through a path (not illustrated) from the controller  103  to select one of the two terminals thereof. 
         [0166]    When the value of the flag ListFLG is “0” and so represents that the slide search process is presently effective, the selectors  131   1 ,  131   2 , . . . , and  131   n  are controlled to supply the outputs of the comparators  111   1 ,  111   2 , . . . , and  111   n  in the slide search unit  100 , which are input to the one input terminals thereof, to the registers  132   1 ,  132   2 , . . . , and  132   n . For example, the selector  131   m  (1≦m≦n) is controlled to select the one input terminal when the value stored in the corresponding register  132   m  is “0.” 
         [0167]    Meanwhile, when the value of the flag ListFLG is “1” and so represents that the list search process is presently effective, the selectors  131   1 ,  131   2 , . . . , and  131   n  are controlled to select and supply the outputs of the comparators  130   1 ,  130   2 , . . . , and  130   n  in the list search unit  102 , which are respectively input to the other input terminals thereof, to the registers  132   1 ,  132   2 , . . . , and  132   n . For example, the selector  131   m  (1≦m≦n) is controlled to select the other input terminal when the value stored in the corresponding register  132   m  is “1.” 
         [0168]    When the outputs of the selectors  131   1 ,  131   2 , . . . , and  131   n  are received, the registers  132   1 ,  132   2 , . . . ,  132   n  output the R flags RFLG 1 , RFLG 2 , . . . , and RFLGn stored therein. That is, the R flags RFLG 1 , RFLG 2 , . . . , and RFLGn stored in the registers  132   1 ,  132   2 , . . . , and  132   n  are updated by the outputs of the selectors  131   1 ,  131   2 , . . . , and  131   n , respectively. 
         [0169]    The R flags RFLG 1 , RFLG 2 , . . . , and RFLGn output from the registers  132   1 ,  132   2 , . . . , and  132   n  are supplied to control terminals of the comparators  130   1 ,  130   2 , . . . , and  130   n  as control signals that control operations of the comparators  130   1 ,  130   2 , . . . , and  130   n . For example, the comparator  130   m  performs a comparison operation when the control signal supplied from the corresponding register  132   m  represents “1” and does not perform a comparison operation when the control signal represents “0.” This means that operations of the comparators  130   1 ,  130   2 , . . . , and  130   n  are narrowed down by outputs of the comparators  130   1 ,  130   2 , . . . , and  130   n  themselves. 
         [0170]    The R flags RFLG 1 , RFLG 2 , . . . , and RFLGn output from the registers  132   1 ,  132   2 , . . . , and  132   n  are also supplied to the address value generating unit  133 . The address value generating unit  133  selects the R flag RFLGm having a value of “1” from the R flags RFLG 1 , RFLG 2 , . . . , and RFLGn supplied from the registers  132   1 ,  132   2 , . . . , and  132   n  and outputs the number of the selected R flag RFLGm as the address value “Address” when the list search process is finished as described above in the process # 5  of  FIG. 4 . The address value “Address” output from the address value generating unit  133  is stored in a register  140  and also supplied to the controller  103 . 
         [0171]    Here, the address value generating unit  133  preferentially selects the R flag RFLGm having a small slide number, that is, the R flag RFLGm based on the slide  120   m  closer to the input side in the slide storage unit  101  when a plurality of R flags RFLGm each having a value of “1” are present. It is because the slide closer to the input has a higher possibility of matching the input data. At this time, the code format described in  FIG. 3  is preferably configured so that one having a small address value “Address” has a short code to increase the efficiency of compression. 
         [0172]    The controller  103  generates the length “Length” and the matching flag FLG representing whether or not there is a match, based on the flag SFINDFLG supplied from the slide search unit  100 , the flag LFINDFLG supplied from the list search unit  102 , and the address value “Address” supplied from the address value generating unit  133 . The length “Length” and the matching flag FLAG are stored in the registers  143  and  142 , respectively. 
         [0173]    The address value “Address”, the data value, the matching flag FLAG, and the length “Length” respectively stored in the registers  140  to  143  are read out to the code format generation processing unit  302  and encoded in a code format as illustrated in  FIG. 3  to generate code data. 
         [0174]    In such a configuration, the slide search process is performed as follows. That is, the comparators  111   1 ,  111   2 , . . . , and  111   n  compare input data with past input data stored in the slides  120   1 ,  120   2 , . . . , and  120   n . The comparison results are supplied to the logical sum circuit  110 , so that the flag. SFINDFLG is output. The comparison results are also supplied to the selectors  131   1 ,  131   2 , . . . , and  131   n  and stored in the registers  132   1 ,  132   2 , . . . , and  132   n  during the slide search process. According to the configuration of  FIG. 11 , this series of processes are executable in one clock. 
         [0175]    Further, the list search process is performed as follows. That is, the comparators  130   1 ,  130   2 , . . . , and  130   n  compare input data with past input data stored in the slides  120   1 ,  120   2 , . . . , and  120   n . At this time, the comparison operations of the comparators  130   1 ,  130   2 , . . . , and  130   n  are controlled based on the values of the R flags RFLG 1 , RFLG 2 , . . . , and RFLGn stored in the registers  132   1 ,  132   2 , . . . , and  132   n . For example, when all of the values of the R flags RFLG 1 , RFLG 2 , . . . , and RFLGn are “0,” all of comparators  130   1 ,  130   2 , . . . , and  130   n  do not perform the comparison operation. This state is a state in which the list search process is not being performed. 
         [0176]    The comparison results by the comparators  130   1 ,  130   2 , . . . , and  130   n  are supplied to the logical sum circuit  18 , so that the flag LFINDFLG is output. The comparison results are supplied to the selectors  131   1 ,  131   2 , . . . , and  131   n , respectively, and stored in the registers  132   1 ,  132   2 , . . . , and  132   n  during the list search process. The R flags RFLG 1 , RFLG 2 , . . . , and RFLGn stored in the registers  132   1 ,  132   2 , . . . , and  132   n  are also held in the address value generating unit  133 . 
         [0177]    The address value generating unit  133  transmits a position of the R flag RFLGm having a value of “1” among the R flags RFLG 1 , RFLG 2 , . . . , and RFLGn held therein to the controller  103  as the address value “Address” when all of the values held in the registers  132   1 ,  132   2 , . . . , and  132   n  are “0.” According to the configuration of  FIG. 11 , this series of processes by the list search process are executable in one clock. 
         [0178]    According to the configuration of  FIG. 11 , the slide search unit  100  and the list search unit  102  are separately configured, and the slide search unit  100  and the list search unit  102  share the slide storage unit  100 . Therefore, it is possible to perform the slide search process by the slide search unit  100  and the list search process by the list search unit  102  in parallel. As described in  FIG. 4 , the waste of one clock upon switchover from the list search process to the slide search process is not generated, and thus the encoding process is able to be speeded up. Further, according to the configuration of  FIG. 11 , since a lookahead buffer or a large-scale matrix array is not required, the hardware scale is reducible. 
         [0179]    &lt;Decoder&gt; 
         [0180]      FIG. 12  illustrates an example of a configuration of the decoder  243 . In the decoder  243 , a code reading unit  400  reads code data encoded by the encoder  242  from the flash memory  240 . The code data read to the code reading unit  400  is supplied to a code format analyzing unit  401 . The code format analyzing unit  401  interprets the code data according to the code format described in  FIG. 3  to extract the data value, the address value “Address,” the length “Length”, and the matching flag FLAG. The extracted data is supplied to a slide expanding unit  402 . 
         [0181]    The slide expanding unit  402  has a slide storage unit including a plurality of registers connected in series in a FIFO configuration as described above with reference to  FIG. 4 . Each register is called a slide and is able to store data of one unit (for example, one byte). The slide expanding unit  402  expands data with respect to each slide in the slide storage unit based on the data value, the address value “Address,” the length “Length,” and the matching flag FLAG, and decodes code data. The decoded data is supplied to a data writing unit  403  and written in the program area  210 A of the main memory  210 . 
         [0182]    &lt;Details of a Decoding Process&gt; 
         [0183]      FIG. 13  is a flowchart illustrating an example of a process of decoding code data encoded by the encoding method of the present embodiment through the decoder  243 . It is assumed that code data is already read from the flash memory  240  by the code reading unit  400 . First, in step S 100 , the code format analyzing unit  401  reads a header of compression data read into the code reading unit  400  and determines whether a subsequent code is the PASS code or the slide code (step S 101 ). 
         [0184]    When the header, that is, the value of the matching flag FLAG is “0,” it is determined that the code having the corresponding header is the PASS code, and the process proceeds to step S 102 . In step S 102 , the code format analyzing unit  401  reads in eight bits subsequent to the header as a data value. The data value is output as output data “as is” (step S 103 ) and supplied to the slide expanding unit  402  to be added to the slide (step S 104 ). The process of adding the data value to the slide is performed by the same procedure as described above in the flowchart of  FIG. 10 . Then, the process proceeds to step S 111 . 
         [0185]    In step S 111 , it is determined whether or not processing has been completed on all of code data read into the code reading unit  400 . When it is determined that it has been completed on all of code data, a series of decoding processes are ended. However, when it is determined that processing has not been completed on all of code data read into the code reading unit  400  yet, the process returns to step S 100 , and the process is performed on a next code. 
         [0186]    When it is determined in step S 101  that the read header is not the PASS code but the slide code, the process proceeds to step S 105 . In step S 105 , the code format analyzing unit  401  reads sixteen bits subsequent to the header as the length “Length” and the address value “Address.” The length “Length” and the address value “Address” are supplied to the slide expanding unit  402 . 
         [0187]    In step S 106 , the slide expanding unit  402  reads the data stored in the slide, represented by the address value “Address” of the slide storage unit. The read data is output as output data (step S 107 ) and also supplied to the slide expanding unit  402  to be added to the slide (step S 108 ). 
         [0188]    The process proceeds to step S 110 , and it is determined whether the length “Length” is larger than “0.” When it is determined that the length “Length” is equal to or less than “0,” the process proceeds to step S 111 . However, when it is determined that the length “Length” is larger than “0”, the process returns to step S 106 . 
         [0189]    &lt;Hardware Configuration of the Slide Expanding Unit&gt; 
         [0190]      FIG. 14  illustrates an exemplary hardware configuration of the slide expanding unit  402 . The slide expanding unit  402  includes a slide storage unit  500 , a controller  501 , and selectors  502  and  503 . 
         [0191]    The controller  501  includes, for example, a microcontroller. The controller  501  receives the address value “Address,” the length “Length,” and the matching flag FLAG and controls an overall operation of the slide expanding unit  402  based on the received data. For example, the controller  501  controls the process of adding the data value to the slide in the slide storage unit  500  or operations of the selectors  502  and  503 . 
         [0192]    The slide storage unit  500  includes: a FIFO configuration with n slides  511   1 ,  511   2 , . . . , and  511   n  which are connected in series and which each include a register and stores data of one unit; and a selector  510  connected to the front of the FIFO configuration. 
         [0193]    Outputs of the slides  511   1 ,  511   2 , . . . , and  511   n  are supplied to the selector  502 . An output of the selector  502  is supplied to the selector  503  and also supplied to the selector  510 . 
         [0194]    The data value read from the code format analyzing unit  401  is supplied to the selector  510  and also supplied to the selector  503 . The selector  510  adds the input data value to the slide  511   1  at the time of the slide adding process in step S 104  of  FIG. 13 . Further, at the time of the slide adding process in step S 104  of  FIG. 13 , data output from the slide selected based on the address value “Address” of the slide code in step S 106  is added to the slide  511   1 . 
         [0195]    At the process in step S 106  of  FIG. 13 , the selector  502  selects an output of the slide  511   Address  from outputs of the slides  511   1 ,  511   2 , . . . , and  511   n  of the slide storage unit  500  based on the address value “Address” supplied from the controller  501  and supplies the selected output to the selectors  503  and  510 . 
         [0196]    In step S 103  of  FIG. 13 , the selector  503  outputs the data value read in step S 102 . Further, at the time of the data output process in step S 107  of  FIG. 13 , the selector  503  outputs the data supplied from the selector  502 . 
         [0197]    The present invention has been described above to be applied to the printer device as one example, but the present invention is not limited thereto. That is, the present invention may be applied to any other device that performs lossless encoding of data using hardware. 
         [0198]    According to the present invention, an encoding process is able to be performed at a higher speed with a small-scale hardware configuration. 
         [0199]    Although the invention has been described with respect to specific embodiments for a complete and clear disclosure, the appended claims are not to be thus limited-but are to be construed as embodying all modifications and alternative constructions that may occur to one skilled in the art that fairly fall within the basic teaching herein set forth.