Method for encoding data

Details Method for encoding data Method for encoding data

1997-12-24

2001-04-17

JeanPierre, Peguy (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

To or from number of pulses

74

Reexamination Certificate

active

06218968

ABSTRACT:

TECHNICAL FIELD OF THE INVENTION
The present invention relates to a method for encoding information, and a method for decoding information. The invention also relates to a device for encoding information and to a device for decoding information.
DESCRIPTION OF RELATED ART
In information processing it is sometimes desirable to transform a message, carrying the information, such that the symbols in the message are adapted to suit a particular purpose. The concept of transforming a message is often referred to as encoding or decoding. Electronic devices for handling information commonly comprises memory units for storing information and display units for displaying said information after retrieval from the memory unit. For the purpose of maximising the amount of storable information in the memory unit, and/or for the purpose of reducing the size of the memory unit the information can be stored in a compressed state in the memory units.
U.S. Pat. No. 5,062,152 relates to a method of processing an analogue signal having an amplitude range with a non-uniform probability density. The method includes quantizing the analogue signal as falling within one of plural signal levels, and assigning a binary code word to the quantization levels in accordance with the occurrence probability of the quantisation levels. According to the method described in U.S. Pat. No. 5,062,152 each code word is predetermined to include eight binary-valued digits.
U.S. Pat. No. 5,488,616 relates to an encoding method. According to U.S. Pat. No. 5,488,616 symbols are provided, each symbol having an occurrence probability. The first method step is to assign a variable-length-code-word to each symbol according to occurrence probability of each symbol. This step uses Huffman coding. Thereafter the variable-length-code-word is coded in two different fashions to provide a first code C
32
and a second code C
34
. In a final step one or both of the codes C
32
, C
34
are selected to provide a reversible variable length code.
SUMMARY
One problem which the invention addresses is to provide a method of encoding a message comprising entities with a non-uniform probability density such that a minimum of band width, or a minimum of power, is required when transmitting the message, e.g. via a radio link.
This problem is addressed by a method for encoding a message. The message comprises a plurality of entities, each entity having an occurrence probability. According to one embodiment of the invention each entity is a character and the method comprises the steps of:
receiving a message;
coding the received message by assigning code words (H), each having plural binary-valued digits, to the received characters (X) so as to generate a binary coded message; wherein
the codewords are assigned to the characters (X) substantially in accordance with the occurrence probability of the characters and the number of bits having a first value (“1”) in the codeword (H) such that characters of higher occurrence probability are assigned codewords with fewer bits having a first value (“1”) than those assigned to characters of lower occurrence probability. The coding method additionally includes generating the binary coded message such that the number of bits in the coded message is minimized.
According to one embodiment the number of bits in the coded message is minimized by: determining a number based on a historical maximum number of mutually different characters; and
selecting a suitable word length for the codewords in response to the determined number of mutually different characters.
When the message to be encoded is in the form of an analogue signal with a non-uniform probability density, the various quantising levels of the analogue signal constitute entities, each entity having an occurrence probability. According to an embodiment of the invention the method comprises:
quantising the signal as falling within one of plural signal level ranges, and
coding the quantised signal by assigning codewords, each having plural binary-valued digits, to the quantising levels so as to generate a binary coded message; wherein
the codewords are assigned to the quantising levels in accordance with the occurrence probability of the quantising levels and the number of bits having a first value (“1”) in the codeword such that quantisation levels of higher occurrence probability are assigned codewords with fewer bits having a first value (“1”) than those assigned to quantisation levels of lower occurrence probability. The coding method additionally includes generating the binary coded message such that the number of bits in the coded message is minimized.
According to one embodiment the number of bits in the coded message is minimized by:
determining a number r of quantising signal levels based on a historical maximum amplitude and a selected amplitude resolution; and
selecting a suitable word length d for the codewords in response to the determined number r of quantising signal levels.
According to another embodiment of the invention the number of bits in the coded message is minimized by compressing the coded message. According to one embodiment this is achieved by encoding the binary coded message in accordance with Huffman coding.
According to a preferred embodiment the binary coded message is interpreted as a first bitstream Y, and the bitstream is subjected to an estimation process whereby a second bitstream E is generated. The estimation process results in a higher proportion of bits having value zero in the second bitstream E than in the first bitstream Y. Additionally the sequence of bits in the second bitstream E resembles the output of a memoryless Bernoulli source. Since the number of bits with value one (“1”) is very low, and since the sequence of bits in the second bitstream E resembles the output of a memoryless Bernoulli source, the conditions for successful Huffman coding are optimized in the second bitstream E. According to the preferred embodiment the second bitstream E is encoded in accordance with Huffman coding.
This method has the advantage of minimizing the number of bits required for transmitting the information content of the message, thereby reducing the band width requirements while minimizing the transmission time and the power required for the transmission.


REFERENCES:
patent: 4168513 (1979-09-01), Hains et al.
patent: 4396906 (1983-08-01), Weaver
patent: 4516246 (1985-05-01), Kenemuth
patent: 4700175 (1987-10-01), Bledsoe
patent: 4813056 (1989-03-01), Fedele
patent: 4841299 (1989-06-01), Weaver
patent: 4899149 (1990-02-01), Kahan
patent: 5059976 (1991-10-01), Ono et al.
patent: 5254990 (1993-10-01), Yoshida et al.
Huffman, A Method for the Construction of Minimum-Redundancy Codes, SMU, The Institute of Radio Engineers, Inc., Sep. '52, vol. 40, No. 9, pp. 1099-1101.
J. Brian Connell, A Huffman-Shannon-Fano Code, Proceedings of the IEEE, Jul. 1973, pp. 1046-1047.

Affiliated with

Also associated with

Rating

Method for encoding 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 encoding data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for encoding data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2521622