System and Method for Multi-Residue Multivariate Data Compression Page: 6
16 p. : ill.View a full description of this patent.
Extracted Text
The following text was automatically extracted from the image on this page using optical character recognition software:
US 9,026,506 B2
1
SYSTEM AND METHOD FOR
MULTI-RESIDUE MULTIVARIATE DATA
COMPRESSION
RELATED APPLICATIONS 5
This application claims benefit of U.S. provisional patent
application 61/619,319, filed Apr. 2, 2012, entitled "SYS-
TEM AND METHOD FOR MULTI-RESIDUE MULTI-
VARIATE DATA COMPRESSION," which is hereby incor- 10
porated by reference for all purposes as if set forth herein.
TECHNICAL FIELD
The present disclosure pertains generally to data compres- 15
sion, and more specifically to a system, hardware implemen-
tation, and method for data compression that utilize multi-
residue multivariate algorithmic processing and/or
semiconductor logic processing.
20
BACKGROUND OF THE INVENTION
There are numerous data compression and encoding algo-
rithms that are known in the art. Each of these different
algorithms has unique aspects that makes it difficult to apply 25
implementation aspects for one algorithm to the implemen-
tation of another algorithm.
SUMMARY OF THE INVENTION
30
A method for encoding data is disclosed that includes
generating a table having N relatively prime moduli, where N
is a positive integer equal to two or more, where each of a
plurality of integers has a unique set of residue values asso-
ciated with the moduli. To encode the data without any error 35
but that of quantization, known as "lossless encoding", a first
data field value of a sequence of L data fields values is stored
or transmitted, where L is an integer equal to or greater than
2. A set of K residue values after the first data value is stored
or transmitted for each of the successive L-1 data field values 40
of the sequence of L data field values until a set of K residue
values for each successive data field value has been stored,
where K<N. To decode the data, the first data field not-
encoded exact value and the L-1 sets of K residue values are
retrieved. The sequence of L data fields is reconstructed using 45
the multi-residue multivariate encoding table and a table
look-up process, using the first exact value and the L-1 sets of
K residue values.
Other systems, choices of moduli, equations and tables,
methods, features, and advantages of the present disclosure 50
will be or become apparent to one with skill in the art upon
examination of the following drawings and detailed descrip-
tion. It is intended that all such additional systems, methods,
features, and advantages be included within this description,
be within the scope of the present disclosure, and be protected 55
by the accompanying claims.
BRIEF DESCRIPTION OF THE SEVERAL
VIEWS OF THE DRAWINGS
60
Aspects of the disclosure can be better understood with
reference to the following drawings. The components in the
drawings are not necessarily to scale, emphasis instead being
placed upon clearly illustrating the principles of the present
disclosure. Moreover, in the drawings, like reference numer- 65
als designate corresponding parts throughout the severalviews, and in which:
2
FIG. 1 is a pictorial description of an exemplary decoding
process where planes at time t and t+a, for consecutive signal
samples are shown;
FIG. 2 is an illustration of a search for the smallest differ-
ence between a known m3 residue of a previous sample and
next-sample values in any one given column of different
numbers that yields a unique shortest distance (difference
between the signal decoded by K moduli and the previous
signal, both less than the product of all the moduli, such
Mm1*m2 for K=2) from the previous solutionto the column
if a table is used of the pair (lx1m, 1x21~2) as an illustration
in the case of two moduli;
FIG. 3 is a diagram showing a function ms3D(ml, m2, m3)
with moduli m=3, m2=5 and m3=7 to generate a 7x15x15
matrix when a direct access to the decoded signal indexed by
three moduli is used instead of searching for speed-up imple-
mentation;
FIG. 4 is a diagram of a system for encoding and decoding
data using multi-residue multivariate compression in accor-
dance with an exemplary embodiment of the present disclo-
sure;
FIG. 5 is a diagram showing exemplary data frame formats
in accordance with an exemplary embodiment of the present
disclosure;
FIG. 6 is a flow chart of an algorithm for multi-residue
multivariate encoding, in accordance with an exemplary
embodiment of the present disclosure; and
FIG. 7 is a flow chart of an algorithm for multi-residue
multivariate encoding, in accordance with an exemplary
embodiment of the present disclosure.
DETAILED DESCRIPTION OF THE INVENTION
In the description that follows, like parts are marked
throughout the specification and drawings with the same ref-
erence numerals. The drawing figures might not be to scale
and certain components can be shown in generalized or sche-
matic form and identified by commercial designations in the
interest of clarity and conciseness.
The disclosed data compression process is based on mul-
tiple residue encoding. As few as three remainders can be
used to encode/compress the data. Prime moduli of type 2n-1
such as (7, 31, 127) have advantages but any other suitable
numbers that are relatively prime composite integers can be
used.
The signal is encoded by the remainder of the moduli
which are chosen to achieve compression. Compression is
accomplished by omitting at least one of the residues in the
compressed transmitted or stored compressed message or
field sequence. The decode/expansion is lossless provided the
signal is bounded in amplitude by the moduli's product and
values. Decoding/expansion can be done by selecting the
value of the encoded signal that is arithmetically closest to the
previous signal value. The selection (decoding) done is based
on the value of a remainder of the amplitude of the known
previous signal and on the transmitted or stored residues
(such as 7 and 31 in one exemplary embodiment, assuming
that 127 is used as the compression residue). The mentioned
residues narrow down the possible values of the missing
remainder. If the maximum peak to peak amplitude of the
signal is less than the product of all the selected moduli (such
as less than7*31*127=27,559 inthe exemplary embodiment)
and the differential between adjacent samples stays below the
production of the transmitted residues, we can guarantee
uniqueness of the selected value. This implies lossless com-
pression except for the unavoidable quantization error whichis insignificant in practice. Likewise, two moduli (like
Upcoming Pages
Here’s what’s next.
Search Inside
This patent can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Patent.
Garcia, Oscar N.; Fu, Shengli & Jaganathan Melaedavattil, Jyothy. System and Method for Multi-Residue Multivariate Data Compression, patent, May 5, 2015; Washington, D.C.. (https://digital.library.unt.edu/ark:/67531/metadc991045/m1/6/: accessed July 18, 2024), University of North Texas Libraries, UNT Digital Library, https://digital.library.unt.edu; crediting UNT College of Engineering.