Coded data generation or conversion – Digital code to digital code converters
Reexamination Certificate
2002-12-20
2004-09-07
Young, Brian (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
C341S051000
Reexamination Certificate
active
06788224
ABSTRACT:
FIELD OF THE INVENTION
This broadly relates to a method for numerical representation that can be advantageously applied to a method for compression and decompression of digital data, while allowing a minimization of selectable degree of the data amount and while maintaining their integrity.
BACKGROUND OF THE INVENTION
It is known that one of the main problems in the computer technology and, more broadly, in the telecommunication technology, lies in the even increasing amount of data to be processed.
This entails a heavy exploitation of computer readable memories, such as removable (for instance CD-ROMS and floppy disks) or fixed (so-called computer Hard Disks) memory medium as well as an extended occupation of the telecommunication networks during information transmission, which, in turn, entails a higher transmission error probability, a higher transmission cost and a physical limitation to the feasibility of real time specific applications. In this regard, some applications can be mentioned in which transmission channels with limited capability are required for transmission of a noticeable amount of data; in detail, mention can be made of the attempt to realise an interactive television system, known as Video-on-Demand, based upon a twin wire telephone network that, due to intrinsic relevant channel limitations, is necessarily bound to transmit a lower data amount, thereby jeopardising the television image resolution.
The present numeric representation of digital data, namely the binary representation, is believed to be the most efficient and reliable.
When it is considered that the amount of information pieces stored in computers and/or exchanged through telecommunication networks is at present rapidly increasing, also due to the strong thrust exerted by the Internet Informatic Network extensively utilising information comprising large data amounts (such as the digital images), the problem of reducing the amount of data representing both information and application programs appears to be extremely critic.
Many approaches have been developed to solve the above mentioned problem, providing for encoding data represented in binary format, according to suitable methods, is in order to reduce the memory occupancy. Such encoding methods are usually particularly advantageous when they are applied to specific data types to be encoded, with specific characteristics. In other words, each individual encoding method turns out to be more or less advantageous according to whether it is applied for instance to data representing stationary images or to data representing video images or to data representing sounds.
The encoding methods can be classified based upon congruence between decoded data and original data or based upon fixed or variable length representation of original data and encoded data.
The first classification type divides the concerned encoding methods into methods having no information loss or “lossless” methods, in which the data reconstructed or decoded from the encoded data are identical to the original ones, and methods having information losses or “lossy” methods, in which the reconstructed data lose a portion of the original data information. Examples of lossless methods are the Run Length Encoding (RLE), the Huffman encoding method and the Lempel-Ziv-Welch or LZW encoding method; an example of lossy method is the Coarser Sampling and/or Quantization or CS&Q method.
According to the second classification type, the RLE and LZW encoding methods entail variable length original data and fixed length encoded data, the Huffman encoding method entails fixed length original data and variable length encoded data, the CS&Q encoding method entails both original data and encoded data with fixed length.
However, just because each encoding method is designed in connection with a specific type of data to be encoded, newer and newer encoding requirements for data having particular characteristics are being encountered.
Furthermore, the search of improved encoding methods aimed at even more compressing the data to be stored and/or transmitted is being even more developed.
SUMMARY OF THE INVENTION
The approach according to various embodiments of the present invention is to be considered in this context.
It is an object of this invention, therefore, to provide a method for numeric representation that is valid for any kind of data, is available to a “lossless” compression and decompression method for digital data, while it enables the data amount to be selectively minimized.
It is specific subject matter of this invention a compression method for compressing an input data binary string, having a number L of bits, to a compressed output data binary string, having a number X of bits, characterized in that at least one sub-string a
n−1
a
n−2
. . . a
1
a
0
(1, 46, 70), having a number n of bits, of the input binary string is construed by assigning a integer numeric value N equal to the sum of the items of a monotonic increasing succession S={s
0
,s
1
,s
2
, . . . } of integer numbers, among the first n items of such succession S, whose corresponding a
i
is equal to “1,” according to formula
N
=
a
n
-
1
·
s
n
-
1
+
a
n
-
2
·
s
n
-
2
+
…
+
a
1
·
s
1
+
a
0
·
s
0
=
∑
i
=
0
n
-
1
a
i
·
s
i
and, for each substring a
n−1
a
n−2
. . . a
1
a
0
, a compressed binary sub-string d
m−1
d
m−2
. . . d
1
d
0
is created, comprising m bits, in which the binary representation of said integer numeric value N, as assigned to the corresponding sub-string a
n−1
a
n−2
. . . a
1
a
0
, is stored, the binary representation of N being furnished by formula
N
=
d
m
-
1
·
2
m
-
1
+
d
m
-
2
·
2
m
-
2
+
…
+
d
1
·
2
1
+
d
0
·
2
0
=
∑
i
=
0
m
-
1
d
i
·
2
i
,
said output data binary string comprising, for each sub-string a
n−1
a
n−2
. . . a
1
a
0
, the corresponding compressed binary sub-string d
m−1
d
m−2
. . . d
1
d
0
and the data of said input binary string lacking of said at least one sub-string an a
n−1
a
n−2
. . . a
1
a
0
, the ratio
R
k
=
s
k
s
k
-
1
,
where k=1, 2, . . . , between two consecutive items of said succession S, fulfilling the condition expressed by formula
R
k
<2 where k≧q≧1,
the number n of bits of said at least one sub-string a
n−1
a
n−2
. . . a
1
a
0
being in the range between a minimum value n
min
and the number L of bits included in said input data binary string, according to formula:
n
min
≦n≦L
the minimum value n
min
being equal to the minimum value of n that fulfills the following condition:
m
=
int
sup
[
log
2
(
∑
i
=
0
n
-
1
s
i
)
]
<
n
where the function y=int
sup
[x] returns the minimum integer value not lower than x (y≧x).
In particular, according to the invention, the first item s
0
of said succession S is equal to 1 (s
0
=1), while the second item s
1
of said succession S is equal to 2 (s
1
=2).
Again according to this invention, the ratio R
k
between two consecutive items of said succession S trends to a constant value R when said index k increases, according to formula
lim
k
→
∞
R
k
=
R
Further according to this invention, said ratio R
k
between two consecutive items of said succession S is never higher than 2, or
R
k
≦2 where k≧1.
Again according to this invention, starting from the (r+1)-th item, or, for k≧r, each item s
k
of said succession S is equal to a polynomial of the p preceding items, where 1≦p≦r, according to formula
s
k
=
∑
h
=
1
p
e
h
·
s
k
-
h
per
k
≥
r
≥
p
,
where the p coefficients e
h
, where h=1, 2, . . . , p, are constant positive, negative or zero integer numeric values.
In particular, the succession S is defined by the following formula:
S
=
S
Fib
=
{
s
0
,
s
1
,
ATOP Innovations S.p.A.
Hunton & Williams LLP
Lauture Joseph
Young Brian
LandOfFree
Method for numeric compression and decompression of binary data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for numeric compression and decompression of binary data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for numeric compression and decompression of binary data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3233549