Method of compressing and expanding data

• US 5,832,037 A
• Filed: 06/24/1996
• Issued: 11/03/1998
• Est. Priority Date: 06/23/1995
• Status: Expired due to Term

• Current Assignee: Hanwha Techwin Co., Ltd. (Hanwha Corporation)
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Park, In-chul
• Primary Examiner(s): Chin, Stephen
• Assistant Examiner(s): Maddox, Michael W.
• Application Number:
  US08/669,704
• Time in Patent Office: 862 Days
• Field of Search: 375/240, 341/50, 341/51, 341/86, 382/232, 382/231, 382/244, 348/384
• US Class Current: 375/240
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction

Abstract

A data compression method and apparatus therefor effects the steps of (a) obtaining an N-bit information word from a bit stream; (b) compressing the N-bit information word into an X-bit information word where X is less than N; (c) obtaining an (N-X)-bit information word from the bit stream; (d) producing a new N-bit information word using the compressed X-bit information word and the (N-X)-bit information word, and (e) repeatedly performing steps (b) through (d) if the new N-bit information word is compressible and otherwise repeatedly performing steps (a) through (d). A data expanding method and apparatus effects includes the steps of: (a) obtaining an (N-X)-bit information word from an N-bit information word, (b) expanding the remaining X-bit information word into an N-bit information word, excluding the (N-X)-bit information word, and (c) repeatedly performing steps (a) and (b) until an N-bit information word is restored. Thus, a bit stream word can be compressed to a fixed length of N bits without loss, and then subsequently expanded.

Claims

1. A data compression method for compressing and storing data contained within a bit stream, the method comprising the steps of:

obtaining an initial N-bit information word from a bit stream of an electrical signal, where N is a positive integer;

compressing said initial N-bit information word into an X-bit information word where X is less than N and where X is a positive integer;

obtaining an (N-X)-bit information word from said bit stream;

producing a new N-bit information word using said compressed X-bit information word and said (N-X)-bit information word; and

repeatedly performing steps of said compressing said N-bit information word, obtaining said (N-X)-bit information word, and producing said new N-bit information word when said new N-bit information word is compressible, and otherwise generating compressed data by repeatedly performing steps of said obtaining said initial N-bit information word, compressing said N-bit information word, obtaining said (N-X)-bit information word, producing said new N-bit information word, and writing said compressed data in a storage medium.

2. A data compression method according to claim 1, wherein said step of compressing said initial N-bit information word comprised substeps of:

(b1) dividing N+1 bits including said initial N-bit information word and 1-bit start information into m data words, m being an integer greater than one, of k bits, where k is a positive integer;

(b2) determining whether there is a difference value smaller than a preset threshold value D among m-1 difference values of m data words and if present, converting one of two data values, whose difference is smaller than said preset threshold value D, into a k-bit information word including 1-bit start information, T-bit flag compression step information, e-bit state conversion information, 1-bit new information, a-bit sequence information of the two data values, and (k-T-2-2a-e)-bit difference value information where D, m, T, e, and a are positive integers;

(b3) inputting 1-bit of new information and repeatedly performing step (b2) until there is no difference value smaller than D among m-1 difference values of m data words with respect to m data words processed in step (b2); and

(b4) repeatedly performing steps (b1) through (b3) if a difference value smaller than D is no longer present among (m-1) difference values of m data words, where k≧

(2a+T+e+2) and D=2^k-T-2-2a-e -1.

3. A data compression method according to claim 1, further comprised of compressing said initial N-bit information word into said X-bit information word where X is less than N and where X is a positive integer, by:

making a reduction in said initial N-bit information word by;

dividing N+1 bits including said initial N-bit information word and 1-bit start information into m data words, m being an integer greater than one, of k bits, where k is a positive integer;

whenever there is a difference value smaller than a preset threshold value D among m-1 difference values of m data words, making a conversion of one of two data values having a difference smaller than said preset threshold value D, into a k-bit information word including 1-bit start information, T-bit flag compression step information, e-bit state conversion information, 1-bit new information, a-bit sequence information of the two data values, and (k-T31 2-2a-e)-bit difference value information where D, m, T, e, and a are positive integers;

inputting 1-bit of new information and repeatedly making said conversion until there is no difference value smaller than D among (m-1) difference values of m data words with respect to m data words processed during said conversion; and

repeatedly performing steps of making said reduction whenever a difference value smaller than D is no longer present among (m-1) difference values of m data words, where k≧

(2a+T+e+2) and D=2^k-T-2-2a-e -1.

4. A data compression method of claim 2, wherein said converted data is placed in a first position of one of the m data words.

5. A data compression method of claim 3, further comprised of placing said converted data into a first position of one of the m data words.

6. A data compression method for compressing and storing data contained within a bit stream, the method comprising the steps of:

(a) obtaining an (N-1)-bit information word from the bit stream of an electronic signal and dividing N bits composed of the (N-1)-bit information word and 1-bit start information into m data words of k bits, where N and k are positive integers;

(b) determining whether there is a difference value smaller than a preset threshold value D among m-1 difference values of m data words, and if so, converting one of two data value into a k-bit information word including 1-bit start information, T-bit flag compression step information, e-bit state conversion information, 1-bit new information, a-bit sequence information of two data values, and (k-T-2-2a-e)-bit difference value information where D, m, T, e and a are positive integers;

(c) inputting 1-bit information and repeatedly performing step (b) until there is no difference value smaller than D among m-1 difference values of m data words processed in step (b);

(d) rearranging m data words according to magnitudes of difference values if there is no difference value smaller than D among m-1 difference values of said m data words, and sequentially storing original sequence information of said rearranged m data words in the order of said rearranged data;

(e) subtracting preset values D_i from the remaining data except for a first rearranged data rearranged in step (d), where 1≦

i≦

m-1;

(f) obtaining the remaining number of bits r obtained by subtracting start information bit number, m·

a, compression step information bit number, new information bit number, and state conversion information bit number from N, obtaining a quotient q by dividing r by m, and determining whether r is smaller than b=k+q(m-1)+f, where f is the number of compression step flag bits;

(g) converting the N bits into start information, compression step information, new information, state conversion information, sequence information, sub-step information, first sorted data, q(m-1)!-bit difference values of subtraction-operated data equal to q bits or less, and the remaining bits of the N bits, if r is greater than or equal to b and difference values are q bits or less, and alternatively converting the N bits into start information, compression step information, new information, state conversion information, sequence information, sub-step information, first sorted data, k+(logm/log2)!-bit display information of one of said subtraction-operated data equal to q bits or more, (q-1)(m-2)!-bit difference values of remaining subtraction-operated data equal to q-1 bits or less, and the remaining bits of the N bits, if r is greater than or equal to b, only one difference value is q bits or more and the remaining bits amount to q-1 bits or less;

(h) converting the N bits into start information, compression step information, new information, state conversion information, sequence information, sub-step information, a first sorted data, (q-1)(m-1)!-bit difference values of subtraction-operated data equal to q-1 bits or less, and remaining bits among N bits, if r is less than b, q is set to (q-1) and all difference values are (q-1) bits or less, and alternatively converting the N bits into start information, compression step information, new information, state conversion information, sequence information, sub-step information, first sorted data, k+(logm/log2)!-bit display information of one of subtraction-operated data equal to (q-1) bits or more, (q-2)×

(m-2)!-bit difference values of the remaining subtraction-operated data equal to (q-2) bits or less, and remaining bits among N bits, if r is less than b, one difference value is (q-1) bits or more and the remaining difference values amount to (q -2) bits or less;

(i) repeatedly performing steps (b) through (h) with respect to the N-bit word stream processed through steps (g) and (h);

(j) terminating compression if none of the conditions of steps (b) through (h) are satisfied, and repeatedly performing steps (a) through (i), where k≧

2a+T+e+2 and k is a positive integer where r exists, D=2^k-T-2-2a-e -1, and N=km, m being an integer greater than one and storing the compressed data.

7. A data compression method for compressing and storing data contained within a bitstream, the method comprising the steps of:

(a) obtaining an (N-1)-bit information word from the bit stream of an electronic signal and dividing N bits composed of an (N-1)-bit information and 1-bit start information into m data words of k bits, where N and a are positive integers;

(b) determining whether there is a difference value smaller than a preset threshold value D among m-1 difference values of m data words, and if so, converting one of two data values into a k-bit information including 1-bit start information word, T-bit flag compression step information, e-bit state conversion information, 1-bit new information, a-bit sequence information of said two data values, and (k-T-2-2a-e)-bit difference value information, where D, M, T, e, and a are positive integers;

(c) inputting 1-bit of new information and repeatedly performing said step (b) until there is no difference value smaller than D among m-1 difference values of m data words processed in step (b);

(d) rearranging m data word according to magnitudes of difference values if there is no difference value smaller than D among m-1 difference values of said m data word, and sequentially storing original sequence information of said rearranged m data words in the order of the rearranged data;

(e) subtracting preset values D_i from the remaining data values except for a first data value rearranged in step (d), where 1≦

i≦

m-1;

(f) obtaining the remaining number of bits r obtained by subtracting start information bit number, m·

a, compression step information bit number, new information bit number, and state conversion information bit number from N, obtaining a quotient q by dividing r by m, and checking whether or not r is smaller than b=k+q(m-1)+f, where f is the number of compression step flag bits;

(g) converting the N bits into start information, compression step information, new information, state conversion information, sequence information, sub-step information, first sorted data, q(m-1)!-bit difference values of subtraction-operated data equal to q bits or less, and the remaining bits of the N bits, if r is greater than or equal to b and all difference values are to q bits or less, and alternatively converting the N bits into start information, compression step information, new information, state conversion information, sequence information, sub-step information, first sorted data, k+(logm/log2)!-bit display information of one kind of the subtraction-operated data equal to q bits or more, (q-1)(m-2)!-bit difference values of remaining subtraction-operated data equal to q-1 bits or less, and the remaining bits of the N bits, if r is greater than or equal to b, only one difference value is q bits or more and the remaining bits are q-1 bits or less;

(h) converting the N bits into start information, compression step information, new information, state conversion information, sequence information, sub-step information, a first sorted data, (q-1)(m-1)!-bit difference values of subtraction-operated data equal to q-1 bits or less, and remaining bits among N bits, if r is less than b, q is set to q-1 and all difference values are q-1 bits or less, and alternatively converting the N bits into start information, compression step information, new information, state conversion information, sequence information, sub-step information, first sorted data, k+(logm/log2)!-bit display information of one of subtraction-operated data equal to q-1 bits or more, (q-2)(m-2)!-bit difference values of the remaining subtraction-operated data equal to q-2 bits or less, and remaining bits among N bits, if r is less than b, one difference value is q-1 bits or more and the remaining difference values are q-2 bits or less;

(i) changing data values using an operation with preset values if the conditions of any of steps (g) and (h) fails to be met;

(j) searching for the case satisfying conditions of steps (b) through (h) with respect to changed data and compressing data according to state conversion information for all preceding steps; and

(k) terminating compression if none of conditions of steps (b) through (j) are satisfied, and repeatedly performing steps (a) through (j), where k≧

2a+T+e+2 and k is a positive integer where r exists, D=2^k-T-2-2a-e -1, and N=km, m being an integer greater than one and storing the compressed data.

8. A data compression method as claimed in claim 7, wherein the operation in step (i) is one of summation, subtraction, and exclusive-ORing.

9. An apparatus for compressing and storing data contained within a bitstream, the apparatus comprising:

a receiving means for receiving an electronic signal and for extracting a bitstream therefrom;

a first obtaining means for obtaining an N-bit information word from said extracted bit stream, where N is a positive integer;

a compression means for compressing the N-bit information word into an X-bit information word where X is less than N and where X is a positive integer;

a second obtaining means for obtaining an (N-X)-bit information word from said extracted bit stream;

a producing means for producing a new N-bit information word using said compressed X-bit information word and said (N-X)-bit information word; and

a control and storage means for causing said compression means through said producing means to repeatedly perform if the new N-bit information word is compressible and for otherwise causing said obtaining means through said producing means to repeatedly perform and for storing the compressed data.

10. An apparatus according to claim 9, wherein said compression means comprises:

a dividing means for dividing N+1 bits including the N-bit information word and 1-bit start information into m data words, m being an integer greater than one, of k bits, where k is a positive integer;

a difference determining means for determining whether there is a difference value smaller than a preset threshold value D among m-1 difference values of m data words and if present, converting one of two data values, whose difference is smaller than said preset threshold value D, into a k-bit information word including 1-bit start information, T-bit flag compression step information, e-bit state conversion information, 1-bit new information, a-bit sequence information of the two data values, and (k-T-2-2a-e)-bit difference value information where D, m, T, e, and a are positive integers;

an inputting means for inputting 1-bit of new information and for causing said difference determining means to repeatedly perform until there is no difference value smaller than D among m-1 difference values of m data words with respect to m data words processed by said seventh means; and

a control means for causing said dividing means through said inputting means to repeatedly perform if a difference value smaller than D is no longer present among m-1 difference values of m data words, where k≧

2a+T+e+2 and D=2^k-T-2-2a-e -1.

11. An apparatus for compressing and storing data contained within a bit stream, the apparatus comprising:

a receiving means for receiving an electronic signal and for extracting a bit stream therefrom;

a first obtaining means for obtaining an (N-1)-bit information word from said extracted bit stream and for dividing N bits composed of the (N-1)-bit information word and 1-bit start information into m data words of k bits, where N and k are positive integers;

a first difference determining means for determining whether there is a difference value smaller than a preset threshold value D among m-1 difference values of m data words, and if so, converting one of two data value into a k-bit information word including 1-bit start information, T-bit flag compression step information, e-bit state conversion information, 1-bit new information, a-bit sequence information of two data values, and (k-T-2-2a-e)-bit difference value information where D, m, T, e and a are positive integers;

an inputting means for inputting 1-bit information and for causing said obtaining means to repeatedly perform until there is no difference value smaller than D among m-1 difference values of m data words processed by said difference determining means;

a rearranging means for rearranging m data words according to magnitudes of difference values if there is no difference value smaller than D among m-1 difference values of said m data words, and for sequentially storing original sequence information of said rearranged m data words in the order of said rearranged data;

a subtracting means for subtracting preset values D_i from the remaining data except for a first rearranged data rearranged by said rearranging means, where 1≦

I≦

m-1;

a second obtaining means for obtaining the remaining number of bits r obtained by subtracting start information bit number, m·

a, compression step information bit number, new information bit number, and state conversion information bit number from N, obtaining a quotient q by dividing r by m, and determining whether r is smaller than b=k+q(m-1)+f, where f is the number of compression step flag bits;

a second difference determining means for converting the N bits into start information, compression step information, new information, state conversion information, sequence information, sub-step information, first sorted data, q(m-1)!-bit difference values of subtraction-operated data equal to q bits or less, and the remaining bits of the N bits, if r is greater than or equal to b and difference values are q bits or less, and for alternatively converting the N bits into start information, compression step information, new information, state conversion information, sequence information, sub-step information, first sorted data, k+(logm/log2)!-bit display information of one of said subtraction-operated data equal to q bits or more, (q-1)(m-2)!-bit difference values of remaining subtraction-operated data equal to q-1 bits or less, and the remaining bits of the N bits, if r is greater than or equal to b, only one difference value is q bits or more and the remaining bits amount to q-1 bits or less;

a third difference determining means for converting the N bits into start information, compression step information, new information, state conversion information, sequence information, sub-step information, a first sorted data, (q-1)(m-1)!-bit difference values of subtraction-operated data equal to q-1 bits or less, and remaining bits among N bits, if r is less than b, q is set to q-1 and all difference values are q-1 bits or less, and for alternatively converting the N bits into start information, compression step information, new information, state conversion information, sequence information, sub-step information, first sorted data, k+(logm/log2)!-bit display information of one of subtraction-operated data equal to q-1 bits or more, (q-2)×

(m-2)!-bit difference values of the remaining subtraction-operated data equal to q-2 bits or less, and remaining bits among N bits, if r is less than b, one difference value is q-1 bits or more and the remaining difference values amount to q-2 bits or less;

a first control means for causing said first difference determining means through said third difference determining means to repeatedly perform with respect to the N-bit word stream processed by said second and third difference determining means;

a control and storage means for terminating compression if none of the conditions effected by said first through third difference determining means are satisfied, and for causing said first difference determining means through first control means to repeatedly perform, where k≧

2a+T+e+2 and k is a positive integer where r exists, D=2^k-T-2-2a-e -1, and N=km, m being an integer greater than one and for storing the compressed data.

12. An apparatus for compressing and storing data contained within a bitstream, the apparatus comprising:

a receiving means for receiving an electronic signal and for extracting a bit stream therefrom;

a first obtaining means for obtaining an (N-1)-bit information word from said extracted bit stream and for dividing N bits composed of an (N-1)-bit information and 1-bit start information into m data words of k bits, where N and a are positive integers;

a first difference determining means for determining whether there is a difference value smaller than a preset threshold value D among m-1 difference values of m data words, and if so, converting one of two data values into a k-bit information including 1-bit start information word, T-bit flag compression step information, e-bit state conversion information, 1-bit new information, a-bit sequence information of said two data values, and (k-T-2-2a-e)-bit difference value information, where D, M, T, e, and a are positive integers;

an inputting means for inputting 1-bit of new information and for causing said first difference determining means to repeatedly performing said step (b) until there is no difference value smaller than D among m-1 difference values of m data words processed by said first difference determining means;

a rearranging means for rearranging m data word according to magnitudes of difference values if there is no difference value smaller than D among m-1 difference values of said m data word, and for sequentially storing original sequence information of said rearranged m data words in the order of the rearranged data;

a subtracting means for subtracting preset values D_i from the remaining data values except for a first data value rearranged by said rearranging means, where 1≦

i≦

m-1;

a second obtaining means for obtaining the remaining number of bits r obtained by subtracting start information bit number, m·

a, compression step information bit number, new information bit number, and state conversion information bit number from N, obtaining a quotient q by dividing r by m, and checking whether or not r is smaller than b=k+q(m-1)+f, where f is the number of compression step flag bits;

a second difference determining means for converting the N bits into start information, compression step information, new information, state conversion information, sequence information, sub-step information, first sorted data, q(m-1)!-bit difference values of subtraction-operated data equal to q bits or less, and the remaining bits of the N bits, if r is greater than or equal to b and all difference values are to q bits or less, and for alternatively converting the N bits into start information, compression step information, new information, state conversion information, sequence information, sub-step information, first sorted data, k+(logm/log2)!-bit display information of one kind of the subtraction-operated data equal to q bits or more, (q-1)(m-2)!-bit difference values of remaining subtraction-operated data equal to q-1 bits or less, and the remaining bits of the N bits, if r is greater than or equal to b, only one difference value is q bits or more and the remaining bits are q-1 bits or less;

a third difference determining means for converting the N bits into start information, compression step information, new information, state conversion information, sequence information, sub-step information, a first sorted data, (q-1)(m-1)!-bit difference values of subtraction-operated data equal to q-1 bits or less, and remaining bits among N bits, if r is less than b, q is set to q-1 and all difference values are q-1 bits or less, and for alternatively converting the N bits into start information, compression step information, new information, state conversion information, sequence information, sub-step information, first sorted data, k+(logm/log2)!-bit display information of one of subtraction-operated data equal to q-1 bits or more, (q-2)(m-2)!-bit difference values of the remaining subtraction-operated data equal to q-2 bits or less, and remaining bits among N bits, if r is less than b, one difference value is q-1 bits or more and the remaining difference values are q-2 bits or less;

a changing means for changing data values using an operation with preset values if the conditions of any of said second or third difference determining means fails to be met;

a first control means for searching for the case satisfying conditions of said first through third difference determining means with respect to changed data and for compressing data according to state conversion information for all of said first obtaining means through third difference determining means; and

a control and storage means for terminating compression if none of conditions of said first difference determining means through said first control means are satisfied, and for causing said first obtaining means through said first control means to repeatedly perform, where k≧

2a+T+e+2 and k is a positive integer where r exists, D=2^k-T-2-2a-e -1, and N=km, m being an integer greater than one and for storing the compressed data.

13. An apparatus as claimed in claim 12, wherein the operation effected by said changing means is one of summation, subtraction, and exclusive-ORing.

14. A data compression and expansion method for compressing and storing data contained within a bit stream and for restoring previously compressed and stored data from the bitstream, the data compression method comprising the steps of:

obtaining an initial N-bit information word from a bit stream of an electrical signal, where N is a positive integer;

compressing said initial N-bit information word into an X-bit information word where X is less than N and where X is a positive integer;

obtaining an (N-X)-bit information word from said bit stream;

producing a new N-bit information word using said compressed X-bit information word and said (N-X)-bit information word; and

repeatedly performing steps of said compressing said N-bit information word, obtaining said (N-X)-bit information word, and producing said new N-bit information word when said new N-bit information word is compressible, and otherwise generating compressed data by repeatedly performing steps of said obtaining said initial N-bit information word, compressing said N-bit information word, obtaining said (N-X)-bit information word, producing said new N-bit information word, and writing said compressed data in a storage medium; and

the data expansion method comprising the steps of;

(a) obtaining an (N-X)-bit information word from a stored N-bit information word obtained from the bitstream of an electronic signal and stored in the memory;

(b) expanding a remaining X-bit information word into an N-bit information word, excluding (N-X)-bit information; and

(c) repeatedly performing steps (a) and (b) until an N-bit information word is restored and storing end outputting the restored bitstream.

15. The data compression and expansion method according to claim 14, wherein said step of compressing said initial N-bit information word comprises substeps of:

(b1) dividing N+1 bits including said initial N-bit information word and 1-bit start information into m data words, m being an integer greater than one, of k bits, where k is a positive integer;

(b2) determining whether there is a difference value smaller than a preset threshold value D among m-1 difference values of m data words and if present, converting one of two data values, whose difference is smaller than said preset threshold value D, into a k-bit information word including 1-bit start information, T-bit flag compression step information, e-bit state conversion information, 1-bit new information, a-bit sequence information of the two data values, and (k-T-2-2a-e)-bit difference value information where D, m, T, e, and a are positive integers;

(b3) inputting 1-bit of new information and repeatedly performing step (b2) until there is no difference value smaller than D among m-1 difference values of m data words with respect to m data words processed in step (b2); and

(b4) repeatedly performing steps (b1) through (b3) if a difference value smaller than D is no longer present among (m-1) difference values of m data words, where k≧

(2a+T+e+2) and D=2^k-t-2-2a-e -1.

16. The data compression and expansion method according to claim 14, further comprised of compressing said initial N-bit information word into said X-bit information word where X is less than N and where X is a positive integer, by:

making a reduction in said initial N-bit information word by;

dividing N+1 bits including said initial N-bit information word and 1-bit start information into m data words, m being an integer greater than one, of k bits, where k is a positive integer;

whenever there is a difference value smaller than a preset threshold value D among m-1 difference values of m data words, making a conversion of one of two data values having a difference smaller than said preset threshold value D, into a k-bit information word including 1-bit start information, T-bit flag compression step information, e-bit state conversion information, 1-bit new information, a-bit sequence information of the two data values, and (k-T-2-2a-e)-bit difference value information where D, m, T, e, and a are positive integers;

inputting 1-bit of new information and repeatedly making said conversion until there is no difference value smaller than D among (m-1) difference values of m data words with respect to m data words processed during said conversion; and

repeatedly performing steps of making said reduction whenever a difference value smaller than D is no longer present among (m-1) difference values of m data words, where k≧

(2a+T+e+2) and D=2^k-T-2-2a-e -1.

17. The data compression and expansion method of claim 15, wherein said converted data is placed in a first position of one of the m data words.

18. The data compression and expansion method of claim 16, further comprised of placing said converted data into a first position of one of the m data words.

19. An apparatus for compressing and storing data contained within a bitstream and for restoring previously compressed and stored data from the bitstream, the apparatus comprising:

a receiving means for receiving an electronic signal and for extracting a bitstream therefrom;

a first obtaining means for obtaining an N-bit information word from said extracted bit stream, where N is a positive integer;

a compression means for compressing the N-bit information word into an X-bit information word where X is less than N and where X is a positive integer;

a second obtaining means for obtaining an (N-X)-bit information word from said extracted bit stream;

a producing means for producing a new N-bit information word using said compressed X-bit information word and said (N-X)-bit information word,

a control and storage means for causing said compression means through said producing means to repeatedly perform if the new N-bit information word is compressible and for otherwise causing said obtaining means through said producing means to repeatedly perform and for storing the compressed data;

a memory for storing previously compressed data extracted from the bit stream of an electronic signal;

an obtaining means for obtaining an (N-X)-bit information word from a stored N-bit information word from the bitstream stored in the memory;

an expanding means for expanding a remaining X-bit information word into an N-bit information word, excluding (N-X)-bit information;

a control means for causing said obtaining means and said expanding means to repeatedly perform until an N-bit information word is restored and for storing it in said memory; and

an output means for outputting the restored bitstream stored in said memory.

20. The apparatus according to claim 19, wherein said compression means comprises:

a dividing means for dividing N+1 bits including the N-bit information word and 1-bit start information into m data words, m being an integer greater than one, of k bits, where k is a positive integer;

a difference determining means for determining whether there is a difference value smaller than a preset threshold value D among m-1 difference values of m data words and if present, converting one of two data values, whose difference is smaller than said preset threshold value D, into a k-bit information word including 1-bit start information, T-bit flag compression step information, e-bit state conversion information, 1-bit new information, a-bit sequence information of the two data values, and (k-T-2-2a-e)-bit difference value information where D, m, T, e, and a are positive integers;

an inputting means for inputting 1-bit of new information and for causing said difference determining means to repeatedly perform until there is no difference value smaller than D among m-1 difference values of m data words with respect to m data words processed by said seventh means; and

a control means for causing said dividing means through said inputting means to repeatedly perform if a difference value smaller than D is no longer present among m-1 difference values of m data words, where k≧

2a+T+e+2 and D=2^k-T-2-2a-e -1.