Title of Invention	"A METHOD FOR ENCODING A MESSAGE"
Abstract	The invention concerns a method for encoding a message, the message comprising a plurality of characters, each character having an occurrence probability; the method comprising 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; characterized in that the coding includes generating the binary coded message such that the number of bits in the coded message is minimized. Representative Figure - Figs. 1A 85 IB.

Title of Invention

"A METHOD FOR ENCODING A MESSAGE"

Abstract

The invention concerns a method for encoding a message, the message comprising a plurality of characters, each character having an occurrence probability; the method comprising 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; characterized in that the coding includes generating the binary coded message such that the number of bits in the coded message is minimized. Representative Figure - Figs. 1A 85 IB.

Full Text	The present invention relates to a system for encoding a message and apparatus for carrying out such method. 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. US 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 US 5,062,152 each code word is predetermined to include eight binary-valued digits. US 5,488,616 relates to an encoding method. According to US 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 C32 and a second code C34. In a final step one or both of the codes C32, C34 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 accor-dance with the occurrence probability of the characters and the number of bits hav-ing 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 em- bodiment 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. Brief description of the drawings For simple understanding of the present invention, it will be described by means of examples and with reference to the accompanying drawings, of which: Figure 1 A is a flow chart illustrating a method for creating a table of correspondence between characters in a human language message and code symbols. Figure 1B is a representation of a transformation table. Figure 2 is a flow chart illustrating a method for data compression according to one embodiment of the invention. Figure 3 A illustrates a set of finite state machines, according to one embodiment of the invention. Figure 3B and 3C is a flow chart illustrating in detail one of the steps in the flow chart according to Figure 2. Figure 3D is an example of a transformation table for co-operation with the finite state machines according to Figure 3 A. Figure 3E is an example of a bit stream. Figure 4 shows a schematic block diagram of a first embodiment of a data compression device according to one embodiment of the invention. Figure 5 is a schematic block diagram of an estimator for use in a data compression device according to Figure 4. Figure 6 is a schematic block diagram of a portable electronic device comprising means for restoring information which has been compressed and stored according to the method described in relation to Figure 2. Figure 7 shows a data restoring device according to one embodiment of the invention. Figure 8 is a flow chart illustrating a method for decoding according to an embodiment of the invention. Figure 9A and 9B is a flow chart illustrating in detail one of the steps in the flow chart according to Figure 8. Figure 10 is a schematic block diagram of a communications system including units for coding and decoding an analogue signal. Detailed description of embodiments A human language comprises certain number of words, and some of these words are more frequently used than others. Each word can be represented by a specific combination of characters, or sometimes by only one character. This means that some characters are more frequently used than others in any one particular language. In electronic devices, such as mobile telephones, there are stored a certain number of predetermined messages, each of which is to be displayed on a display unit of the mobile telephone in response to a certain event. Commonly these messages are stored in a read-only memory. In order to display a message the corresponding data is read from the memory and for each character the corresponding ASCII-code is delivered to the display unit, which in response thereto displays a combination of ASCII-codes constituting the selected message. As stated above, some characters have a higher relative frequency than others in one particular human language or in one particular predetermined set of messages. The present invention relates to a method for reducing the number of bits necessary for representing information in a predetermined language and/or for reducing the num-ber of bits necessary for representing a predetermined set of messages in any language. A Method for Creating a Transformation Table Figure 1A is a flow chart illustrating a method for obtaining a transformation table such that the character in a chosen set of messages, or the characters in a selected language, can be transformed into code symbols such that the total Hamming weight of messages of the selected type will be minimised. A symbol may comprise one or a plurality of components. According to the preferred embodiment the each code symbol is a combination of binary digits. The Hamming weight is minimised when the number of digits having value "1" is minimised. By transforming all the characters into corresponding Hamming symbols two important objects are achieved. The first object is that of assigning a weight to each character. As described below, a lower Hamming weight also leads to a larger compressibility of the symbol, thereby providing a link between the Hamming weight and the memory space required for storing the symbol. Secondly, the trans-formation into Hamming symbols in the manner described below reduces the weight difference between two consecutive characters in the message. In other words the number of digit positions which are different in a second symbol as compared to a first symbol is reduced. With reference to Figure 1A a first step S10 is to select a human language. The se-lected human language could be for example English, French, Swedish or any other human language which uses characters for composing messages. A variable is assigned the name of the selected language, and this language identifying variable is saved for identifying the table to be created. In step S20 a complete set of messages is received. The number of characters in a complete set of messages could be for example 2500. According to one embodiment of the invention each character is composed of 8 bits. In step S30 the number of mutually different characters are counted and a variable r is assigned the count value. In a typical alphabet the number of mutually different characters may be for example 64. In step S40 the relative frequency for each character is calculated, and in step S50 the characters are sorted in order of decreasing relative frequency. In other words the most commonly used character is placed first in the list and the most infrequent character is placed last in the list. An example of such a list is shown in Figure IB. In Figure IB is shown a memory unit 10 having a plurality of memory positions 20. Each memory position may for example comprise 8 bits. The first memory position is provided with the language identifying variable, which may for example be the letter E identifying that the list/table comprises characters used in a set of English language messages. The second memory position in the list indicates the number of characters stored in this particular list. In this example the number of different char-acters is 64. The third memory position contains the ASCII-code for the character which has the highest relative frequency pi. hi this example the most frequent char-acter is "H". In the fourth memory position is stored the character (hi this example "G" having the second highest relative frequency p2. In this manner the 64 different characters are placed in the list such that the character having the lowest relative frequency P64 is placed in the last position in the list. In step S60 a symbol having only zeros (0) is assigned to the character having the highest relative frequency pi. In the example shown in Figure 1B the selected set of messages contained only 64 different characters, and therefore the symbol to be as-signed to the first character is a symbol comprising six digits, all of which are zero. According to the invention there is created a list of symbols, herein referred to as Hamming symbols, of increasing Hamming weight. The Hamming symbols are as-signed to the characters in the list so that the character having the highest relative frequency p1 is assigned a Hamming symbol having a lowest Hamming weight. The character having the lowest relative frequency p64 is assigned a Hamming sym-bol having a Hamming weight which is not lower than any of the other Hamming symbols. However, with the knowledge that the first Hamming symbol is a symbol with six digits, all of which are zero it is possible to calculate the subsequent Hamming symbol having a weight which is at most one weight step higher. According to the invention, therefore, it is not necessary to actually store a complete list of Hamming symbols. Instead it is sufficient to identify how many digits there are to be in the Hamming symbols. Since the number of digits required in the Hamming symbols can be calculated having knowledge of the number of characters, it is only necessary to have a predetermined manner of calculating subsequent Hamming symbols starting from a first Hamming symbol containing only zeros. In step S70 a table of correspondence is created and the table is delivered to a mem-ory unit for storage, as will be described below. Since none of the Hamming sym-bols actually needs to be stored, the list of correspondence only needs to include a variable indicating the name of the list, a figure indicating the number of characters in the list and the characters in order of decreasing relative frequency. Using this minimum amount of information it is possible to calculate the value of each Ham-ming symbol to be assigned to each character, which is the only information neces-sary for creating a table of correspondence. Accordingly, since it is only necessary to store a list of characters and a control word (the figure indicating the number of characters) a very small amount of memory space is needed for the table of corre-spondence. A method for transforming a message Figure 2 is a flow chart illustrating a method for transforming a message into a bit stream, such that the bit stream has a minimal number of digits. According to a first step S1 00 of an embodiment of the method, a message ML com-prising a plurality of characters X is transformed into a bit stream Y.. This is achieved by receiving the message ML (step S 110), and transforming each character X into a corresponding symbol H, using a table as described above in connection with Figures 1B and 1A. According to step S120 consecutive characters in the mes-sage are consecutively transformed into symbols such that a stream of symbols H is provided. According to the next step S130 of the method the generated symbols H are delivered as a bit stream. According to step S140 the bit stream Y is provided to an estimator for transforming the received bit stream into a second bit stream E. The purpose of step S140 is to provide a second bit stream E consisting mostly of zeros (0) in response to the bit stream produced by step S130. Another purpose of step S140 is to provide a second bit stream E whose digits are as close as possible to random variables which are in-dependently and identically distributed. Step S140 is described in more detail with reference to Figure 3 below. According to step S150 the second bit stream produced in step S140 is compressed in accordance with a compression algorithm. According to one embodiment of the invention the compression algorithm used is Huffman coding. For detailed informa-tion about Huffman coding the reader is referred to D.A. Huffman. "A method for the construction of minimum redundancy codes." Proc. IRE, 40:1098-1101, 1952. The compression step S150 generates a third bit stream C having fewer digits than the second bit stream. In fact the method as described above reduces a message ME in the English language to a mere 57.8% of the original number of bits. This figure was achieved for a full set of status messages for cellular phones, where the original messages in English required a size of 2323 bytes. The compression ratio of 0,578 includes the transformation table used for transforming the characters into corre-sponding Hamming symbols. This means that the actual compression ratio of the message, assuming the transformation table is available at the receiving end where the message is to be retrieved, is even better. According to step S160 the third bit stream which is generated by step S150 is stored into a memory device. Alternatively the third bit stream provided by step S150 is delivered to an output for transmitting it to another electronic device. According to the invention an advantageous compression ratio is achieved in the above manner. The above information transformation method is therefore suitable for transforming messages into compressed bit streams before storing the message in a memory device, since the transformed message requires substantially less memory space than the original message. In the table below are provided examples of text messages in eleven different languages, and the corresponding compression ratio achieved when the message was compressed. The compression ratio is calculated as the size of the compressed message plus the size of the transformation table divided by the size of the original set of messages. (Table Removed) TABLE 1 It is clear from the above examples (see TABLE 1) that the compression ratio is nearly independent of the language used in the original message. Step S140 is described in more detail with reference to Figures 3 A, 3B and 3C. Since the method described with reference to Figure 3B and 3C uses a set of finite state machines, an example of such a set of finite state machines is shown in Figure 3 A. For the purpose of executing the method according to step S140 in accordance with a preferred embodiment of the invention there is used a set of finite state ma-chines having k'2m different states. According to a preferred embodiment the parameters k and m are chosen as follows: k = 6, and m = 10. Parameter k is chosen to 6 because there are not more than 26 characters in an alphabet usually used in the messages to be coded according to the preferred embodiment. The parameter m is selected sufficiently large to provide a sufficient "history" and small enough to avoid problems with poor statistics in each state. Another consideration for the choice of parameter m is to select it to a suitable value depending on the availability of memory for the counters producing the count values V, as described below with reference to Fig 5 and 3C. For the purpose of illustrating the underlying principle of the method a set of finite state machines having only 3 22 states is shown in Figure 3 A. Thus the set of finite state machines shown in Figure 3 A is based on k = 3 and m = 2. The fact that m = 2 means that each state is defined by two digits, as illustrated in Figure 3 A. The set of finite state machines in Figure 3 A consists of three different finite state machines 110, 120 and 130 since k equals 3. Each of the circles shown in Figure 3 A illus-trates a state in the set of finite state machines 110, 120, 130, and according to the invention there is a count value V provided in each state in the set of finite state ma-chines. In this manner the set of finite state machines according to Figure 3 A has a total of 12 different count values, each of which will be individually controlled in accordance with the method which will be described below. In the following example, it is assumed that a set of messages has been analysed, according to the method described in connection with Figure 1A, such that a table of correspondence between characters X and symbols H in accordance with Figure 3D has been established. In a real case the characters X would be shown in for ex-ample ASCII-codes, and the list of characters would be proceeded by a number in-dicating the number of characters in the list, but for sake of simplicity in this expla-nation the table of correspondence is shown as a direct table of correspondence between alphabetic characters and 3-digit Hamming codes. The list in Figure 3D shows eight characters hi order of decreasing relative frequency and corresponding Hamming symbols in order of increasing Hamming weight. With reference to Figure 3B step S200 indicates the method step of receiving a mes-sage in the form of a sequential bit stream Y = y1, y2, y3,... yn such as the bit stream shown in Figure 3E. In the next step S210 the estimator produces output digits Cj, which for the first m digits equals the input digits yi. In step S220 the value i is set torn. In the following step S230 a number, k, of finite state machines are set up. In other words, a set of finite state machines comprising k different finite state machines are defined. Each finite state machine comprises 2m states, and there is a count value V in each state. In step S230 all the count values V in the set of finite state machines are set to zero. The finite state machines are ordered such that there are machines Ml M2,.. Mj ...Mk. With reference to step S240 in Figure 3B the following procedure will start from finite state machine Mj, where j= (m mod k)+l. In the selected finite state ma-chine, state S=(y1, y2, ... ym) is initially selected. In the selected state, the value V is read (step S250), and thereafter (step S260) there is a check if the V>0. If V>0 a prediction value pi+1 is set to one (1), as indi-cated by box S270 in Fig 3B. If V With reference to Figure 3B and Figure 3E the next input digit yi+1 is read (step S290), and the output value ei+1 is calculated, in step S300), by adding yi+1 and pi+1 modulo 2. Hence, 1+1 modulo 2 equals zero, 1+0 modulo 2 equals 1, and 0+1 modulo 2 equals 1. Next, in step S310, there is a check of the value of digit yi+1. If yi+1l the count value V, in the selected state in the selected finite state machine, is increased by 1, i.e. V :=V+1, as illustrated in box S320 in Fig 3C. If yi+1=0 the count value V, in the selected state in the selected finite state machine, is decreased by 1, i.e. V :=V-1, as illustrated in box S330 in Fig 3C. Thereafter, in step S340, the next finite state machine Mj+i is selected. In the selected finite state machine: the state indicated by the value of digit yi+1 and the previous state (Step S350) is selected. This is done in the manner commonly used for changing from one state to another state within one finite state machine. For example, with reference to Fig 3 A, when starting from state "00" in the first finite state machine 110 and the digit yj+1 is a "1" state "01" is selected in the sec-ond finite state machine 120, in accordance with the invention. When the current state is state "01" in the second finite state machine 120 and the digit yi+1 is a "1" there will be a transition to state "11" in the third finite state machine 130. If the current finite state machine is the last (k:th) finite state machine then there will be a transition to a state in the first finite state machine in the same manner. Thereafter the index value i is increased by one, as indicated by box S360. Thereaf-ter there is a control if any further bits remain in the received bit stream Y, as indi-cated by step S370 in Figure 3C, and if the answer is "yes" we proceed again with step S250, reading the count value V in the selected state of the selected finite state machine. If, on the other hand, this was the last bit in the message the procedure is ended. A data compression device With reference to Figure 4 there is shown a block diagram of a first embodiment of a data compression device 200. The data compression device comprises a character input 210 for receiving characters of a message to be transformed. The character in-put 210 is coupled to a conversion unit 220 by means of a data bus 230. The data bus is capable of transferring eight digit characters in parallel, in accordance to one embodiment of the invention. According to another embodiment of the invention the digits in the received characters are delivered in series to the conversion unit 220. Also, a character to be received at the character input 210 may comprise another number of digits. The conversion unit is set up to convert the received characters into symbols having a low Hamming weight, in the manner described above with reference to steps S110 and S120 in Figure 2. The resulting symbol, which may comprise a lower number of digits than the corresponding character, is delivered from output 234 via a bus 240 to the input 242 of a symbol-to-bit-stream converter 250. The symbol-to-bit-stream converter 250 delivers, on its output 252 a bit stream with digits yi to an input 254 of an estimator unit 260. The purpose of the estimator unit 260 is to further reduce the number of digits having the value " 1" in the bit stream, while maintaining the information content in the message. The estimator unit 260 produces a bit stream E=e1en in response to reception of a bit stream Y=y1-yn, where n is the number of digits in the bit stream provided to the estimator unit 260. The bit stream E is delivered on an output 262 of the estimator unit 260. The bit stream E is delivered to a compression module 270 which is set up to reduce the number of digits in the bit stream while maintaining the information content in the message. The compression module operates in accordance with a compression algorithm, such as for example Huffman coding. According to a preferred embodi-ment a static Huffman code is used. Hence the compression module 270 produces a bit stream C=Ci-cr, where r With reference to Figure 5 the estimator unit 260 is described in more detail. The estimator unit 260 has a series input 300 for receiving the bit stream Y comprising the bits yi. The received bits yi are delivered to a switch unit 310 which is set up to switch the first m digits directly to an output 320. The bit stream input 300 is also coupled to a first input 340 of a modulo 2 adder 350, and, via a delay unit 355, to a predictor unit 330. The delay unit 355 remembers one bit such that it delivers bit y; when receiving bit yi+1. The predictor unit 330 has an output which is coupled to a second input 360 of the adder 350. The adder 350 has an output which is coupled to the estimator unit output 320. The estimator 260 is thus set up to perform the method described above with reference to Figure 3B and 3C. In the above described manner the predictor unit 330 is set up to make a prediction Pi+i of the value of the next bit yi+1. In other words the predictor unit 330 is set up to "guess" what value the bit yi+1 has, basing the "guess" pi+1 on the historical values yh for h The value Ci+1 represents the Hamming distance between the predicted bit value pi+1 and the actual bit value yi+1. Thus the Hamming distance ei+1 between two succes-sive bits is zero (0) if the predictor makes correct predictions. It is clear from the above, with reference to table 1, that the method according to the invention achieves very favourable compression ratios. One of the causes for this advantageous result is accurate predictions pi+1 in accordance with the described prediction method. As described below, with reference to Fig 9, the decoding method is based on doing the same type of prediction, using the already decoded bit values y, as "history" for achieving a value pj+i representing a prediction of the next Hamming distance Ci+1. Since the predictive decoding method uses the same type of prediction as the pre-dictive coding does, the result of the decoding will be the correct bit stream Y . An electronic data processing device With reference to Figure 6 there is shown a data processing device 400 comprising a display unit 410 for the display of information such as text messages. The data processing device 400 comprises a non volatile memory 420, a microprocessor 430 and a read/write memory 440. The memory 420 has a first memory portion 450 wherein a computer program is stored for controlling the normal functions of the data processing device 400. The data processing device may be for example a port-able electronic device such as a mobile telephone. The memory 420 also has a sec-ond memory portion 460, where a program for coding and/or decoding messages is stored. In another embodiment the program for coding and/or decoding messages is stored on a separate non-volatile recording medium 462. The program may be stored in an executable manner or in a compressed state. When, in the following, it is described that the microprocessor 430 performs a cer-tain function this is to be understood that the microprocessor performs a certain part of the program which is stored in the memory 450 or a certain part of the program which is stored on the recording medium 462. The microprocessor 430 is coupled to the display unit 410 via a data bus 470. A user of the data processing device is provided with information messages by means of characters being displayed on the display 410. A particular message may be dis-played in response to a certain event, such as for example the microprocessor hav-ing determined that the battery voltage in the electronic device is lower than a certain value, which prompts the microprocessor to display the message "CHANGE BATTERY". The microprocessor 430 is coupled to the memory 420 by means of a data bus 480, and to the read/write memory 440 by means of a data bus 490. The microprocessor 430 also communicates with a data port 500 by means of a data bus 510. The methods described with reference to Figures 1A, IB, 2, 3A-3D can be per-formed by the microprocessor 430 by means of the microprocessor performing the program stored in the memory portion 460. In response to an instruction to create a table of correspondence, in accordance to the method described with reference to Figure 1A, the microprocessor is set up to wait for reception of a message on the data port 500 and as the message is received on the data port 500 the characters are temporarily stored in the read/write memory 440. When all the characters of the re-ceived message, or of the received set of messages, have been temporarily stored, the microprocessor is set up to count the number of different characters and to cal-culate the relative frequency for each character. Thereafter the microprocessor 430 is set up to assign code symbols to the different characters in the manner described above, such that a table of correspondence is created. Alternatively the microprocessor is set up to receive a ready made table of corre-spondence via the data port 500 and to store that table of correspondence in the read/write memory 440. As described with reference to Figure IB the table of corre-spondence may be limited to a list starting with a number, and followed by the same number of characters. Thereafter the microprocessor may respond to an instruction for transforming the received message, or the received set of messages, into a reduced digit bit stream E, in accordance with the method described above with reference to Figure 3B. When the message, or the set of messages, have been transformed into a bit stream this bit stream is stored in the memory 440. The microprocessor may of course be set up to store the bit stream E bit by bit or sorted in for example eight bit words, depending on the most efficient way of operating the memory which is used, or depending on other hardware considerations. A data restoring device With reference to Figure 7 a block diagram of a first embodiment of a data restoring device 600 is described. The data restoring device comprises an input 610 for re-ceiving a compressed bit stream C consisting of a number of digits cj. The input 610 is coupled to a decompression module 620, which is arranged to expand the bit stream C into a longer bit stream E while maintaining the information content. The decompression module 620 may be set up to perform decoding in accordance with a static Huffman code. The decompression module 620 delivers the expanded bit stream E to an input 622 of a transformation unit 630 which is set up to perform substantially the reverse function of the estimator 260 which is described above. Hence the transformation unit 630 delivers a bit stream Y comprising a number of symbols H in series. For this purpose the estimator 260 includes a switch 632 functioning as switch 310 in fig 5. A delay unit 634 delivers bit y; on reception of bit yi+i, in analogy with unit 355 in fig 5, and a predictor unit 635 generates prediction values pi+1 in response to receiving the "historical" values y;. Whereas the predictor unit 330 in the encoder 260 is coupled in a feed-forward fashion, the predictor 635 in the decoder 630 is coupled in a feed-back fashion such that the output Y is used as "historical" data for decoding the input bit string E. The transformation unit 630 is set up to deliver the bit stream Y to an output 638. A converter 640 is coupled to the output 638 for converting the bit stream to symbols. The symbols H are delivered, via a data bus, to an input 642 of a conversion unit 650. The conversion unit 650 operates to convert the symbols H into characters X, such that the original message is restored. The characters X are delivered from the conversion unit 650 to an output 660. The characters delivered on the port 660 may be for example eight bit ASCII-codes. A method for restoring a message Figure 8 is a flow chart illustrating a method for restoring a message M from a com-pressed bit stream C, in accordance with one embodiment of the invention. Accord-ing to a first step S600 a compressed bit stream C is received. The bit stream C is expanded into a bit stream E (step S610) using a known method for decod-ing/expanding, such as Huffman decoding. The bit stream E is then transformed into a bit stream Y, essentially by performing the method described with reference to Figures 3B and 3C in reverse (S620). Thereafter the bit stream Y is transformed into characters X such that the original message M is restored (step S630). This is achieved by dividing the bit stream Y into symbols H (S640), and thereafter transforming each symbol H into a corre-sponding character X (step S650). The transformation of symbols H into characters X is performed using a table of correspondence which was also included in the compressed bit stream C. Alternatively the transformation table is already provided and the compressed bit stream C includes only information to be transformed into a message. According to a third embodiment of the symbol-to-character transforma-tion step, the compressed bit stream only comprises a number indicating the number of different characters in the message and a list of the characters. For the purpose of obtaining the transformation table a microprocessor, such as the microprocessor 430 (see Figure 6) may be set up to calculate the symbols H corresponding to each char-acter X in accordance with a predetermined algorithm which may be provided in the program stored in the memory portion 460 (Figure 6). When the symbols H have been transformed into characters X the resulting message is delivered. With reference to Figure 6 the compressed bit stream C may be provided in a mem-ory portion 700 in the non volatile memory 420. In response to a message presenta-tion instruction the microprocessor 430 may, using the program stored in the mem- ory portion 450, use a standard expansion algorithm for decompressing a data re-storing program which was stored in a program portion 710 of the memory 450. The program code stored in memory portion 710 is thus expanded and positioned in a memory portion 720 of the memory 440. As mentioned above the memory 440 may be a random access memory RAM. The microprocessor thereafter continues by exe-cuting the data restoring program from the memory portion 720. The execution of ,the data restoring program includes the step of reading the compressed bit stream C from the memory portion 700 in the non volatile memory 420 and thereafter execut-ing the method steps S610, S620, S640 and S650 such that the compressed bit stream C is transformed into a stream of characters X constituting a message M. The message M, or parts of the message, are delivered by the microprocessor 430 to the display unit 410 via the data bus 470. Alternatively, depending on the circum-stances, the message M may be delivered to the data port 500 via the data bus 510. With reference to Figures 9A and 9B there is described in detail how the transfor-mation of bit stream E into a bit stream Y (S620 in Figure 8) is performed. The method described with reference to Figures 9A and 9B is herein referred to as a predictive decoding method, and the method described above with reference to Fig-ures 3B and 3C is herein referred to as a predictive encoding method. The predictive decoding is performed essentially in the same manner as the predictive encoding, as is clear by comparing the flow chart according to Figure 9 with the flow chart ac-cording to Figures 3B and 3C. Thus the method steps S700 to S870 essentially cor-respond to the method steps S200 to S370 described above. The difference between the decoding and the encoding is essentially that whereas in the encoding method digit yi+1 is read from the input (S290) and the digit ei+1 is calculated, the opposite is true in the decoding method. With reference to Figure 9B the input digit ei+1 is read and the output digit yi+1 is calculated. Hence in step S810 in the decoding method the question about the value yi+i relates to the question of whether the output digit equals one or zero, whereas in the encoding method step S310 relates to the ques-tion of the value of the input value With reference to Figure 6 the data restoring program in the memory portion 710 can be limited to a program routine defining the difference between the encoding and the decoding method. Thus there is a very small difference in the use of mem-ory space between on the one hand storing only the decoding program in the mem-ory and on the other hand storing the decoding program as well as the encoding program. Furthermore the skilled reader will realise that the above described coding methods and decoding methods require so advantageously few and mathematically uncomplicated steps that the program in itself will require an advantageously small amount of memory space. Hence a computer program for decoding and/or for en-coding messages according to the invention is particularly advantageous in portable electronic devices where the use of memory space for program code directly trans-lates into the size of the device. In mobile telephones, for example, a large number of messages need to be stored in the memory, and each telephone shall preferably be settable to produce the messages in a human language selected by the user. It is therefore an object of the present invention to provide a large number of such mes-sage sets in a small amount of memory space in a non volatile memory in the mobile telephone. Since the decoding program according to the invention requires such a small amount of memory space all the different language messages may be stored in a coded state, and when the user has selected the language in which he/she wants to see messages, the selected set of messages will be decoded in accordance with the above described method. A maximum amount of memory space is used during the execution of the predictive encoding and/or the predictive decoding program, since a number of count values V need to be temporarily stored during the execution of the program. Denoting the number of bits for each count value by c, the number of bits needed for storing the count values is k 2m c. According to the preferred em-bodiment the value of c may be selected to equal 2 or 3. In the above described embodiments the Hamming weight of the message is de-creased for the purpose of providing an encoded message suitable for compression A suitable Huffman code provides a more efficient compression the lower the Hamming weight of the message to be compressed. However, by the choice of a dif- ferent Huffman code a more efficient compression is achieved the higher the Hamming weight of the message to be compressed. Thus, according to the inven-tion, the transformation of characters into code symbols can be done in such a man-ner that the Hamming weight of the encoded message is maximised. In this case, the predictive encoding method is modified such that it strives to generate a bit stream E having a higher Hamming weight than the of the input bit stream Y. A Communications Network Figure 10 shows a communications network 735 including two units 740 and 750 communicating via a radio link. The unit 740 includes a microphone 760 for gen-erating an analogue signal, and a conversion unit 770 for quantising the analogue signal into a plurality of quantising ranges and assigning codewords H to the quan-tising ranges. Hence, on receiving an analogue signal the conversion unit 770 delivers a sequence of codewords H in the form of a bitstream Y. According to a preferred embodiment the bitstream Y is delivered to an estimator unit 260, of the type described in detail above. The output E of the estimator unit is delivered to a compression module 270, also operating as described above. The compressed bit stream C delivered by the compression module 270 is delivered to a transceiver 780. The transceiver 780 in-cludes a communications port 790, e.g. an antenna, for communicating with the unit 750. The unit 750 includes a communications port 800, e.g. an antenna, coupled to a transceiver 810 for receiving and delivering signals. The transceiver 810 is coupled to a decompression module 620 of the type described above, for translating a com-pressed bitstream C into a decompressed bitstream E. The decompressed bitstream E is delivered to a decoder 630 of the type described above in connection with Fig. 7. The output Y of the decoder 630 is delivered to a conversion unit 820. The conversion unit 820 converts the received bitstream Y into an analogue signal, which is delivered e.g. to a loudspeaker 850. The conversion unit 820 includes a controller 825 and a memory 830 in which con-version information including a conversion table is stored. The memory 830 holds information about the word length of the codewords H. Using that information, the received bitstream Y is divided into codewords H by the controller 825. The codewords H are subsequently delivered to a digital-to-analogue (D/A) con-verter 840. The D/A converter 840 co-operates with the conversion table in the memory 830 to generate the signal levels defined by the codewords H. When the codewords H are fed to the D/A-converter 840 at the same frequency with which the original signal was sampled, the output of the D/A-converter will resemble the original analogue signal. The function of the conversion unit 770 is as follows: The conversion unit 770 re-ceives an analogue signal having an amplitude with a non-uniform probability den-sity. The amplitude probability e.g. for speech has a maximum for zero amplitude, and decreases with increasing amplitude. Thus, after quantisation of a speech signal the most probable quantization level ranges are those corresponding to the lowest amplitudes. For the purpose of minimizing the Hamming weight of the A/D-converted signal Y, the codewords H should be selected to minimize the number of bits having value "1" (one). A coding scheme for assigning codewords, with a minimum of zeros, to an analogue signal is described in US 5,062,152, the content of which is hereby incorporated by reference. Advantageously, the digital signal Y delivered by the conversion unit 770 can be minimized by adapting the word length of the codeword H to the required number r of quantising levels. If, for example, it is sufficient to have r=64 quantising levels the code symbols need only include six bits. If the number of quantising levels is between 65 and 128, a word length of seven (7) bits is required. The number r of quantising levels definable by a word with d bits is: r = 2d The necessary number of bits d hi the codeword H can therefore be established us-ing the following equation: d1 = ln(r)/ In2 If the result di is not an integer the number of bits d are established by rounding di up to the closest higher integer. If, for example, the required number of quantising levels is r = 190, the result d1= In(170)/ln2 = 7,409. Rounding d1 to the closest higher integer renders d=8. Hence, the required number of bits in the codewords H is d=8. The word length d of the codewords H is transmitted to the unit 750 and stored in memory 830. The variable d is used by controller 825 for dividing the bit-stream Y into codewords of the correct length upon reception of coded messages. The required number of quantising signal ranges depends on the maximum ampli-tude of the analogue signal and of the amplitude resolution. For high fidelity repro-duction of the analogue signal the level ranges should be small so as to achieve a high amplitude resolution, hence a large number of quantising signal levels should be used. For the purpose of establishing a maximum amplitude of the analogue signal the signal is measured for a certain time duration. The amplitude resolution can be set manually or automatically. By adapting the word length of the codewords to a his-torical maximum amplitude and a selected amplitude resolution the number of bits is minimized in the digital signal Y. The conversion unit 770 generates a list of concordance between quantising signal ranges and codewords, i.e. a conversion table. The list is stored in a memory 860 co-operating with the conversion unit 770. The list stored in a memory 860 is used for assigning code words H to quantising signal ranges in accordance with the es-tablished concordance. Additionally the list of concordance and the word length d is delivered from con-version unit 770 to the transceiver 780 for transmission to the unit 750. On recep-tion of the list of concordance by transceiver 810, the list is delivered to conversion unit 820 for storage in the memory 830. The list stored in the memory 830 is there-after used by the D/A converter 840 for generating the signal levels defined by the codewords H According to another embodiment of the communications network 735 the coded message, including the codewords H, is delivered directly from the conversion unit 770 to the transceiver 780, as indicated by dashed line 870 in Fig. 10. In that em-bodiment the receiving unit 750 also provides a direct connection 880 between the conversion unit 820 and the transceiver 810. According to yet another embodiment of the communications network 735 the coded message including the codewords H is delivered directly from the conversion unit 770 to the compression module 270. The direct connection is obtained by a data bus, indicated by dashed line 882 in Fig 10. The unit 750 includes a corresponding data bus 884, providing a direct connection between the decompression module 620 and the conversion unit 820. The direct connection by data bus 884 enables a re-duction of the number of bits in the encoded message delivered by conversion unit 770. According to yet another embodiment there is a direct connection 890 between the estimator unit 260 and the transceiver 780 thereby allowing transmission of the bit-stream E, which holds fewer zeros than the bitstream Y. Hence this embodiment has the advantage of further reducing the power required to transmit signals such as speech or music having non-uniform probability densities. The unit 750 includes a corresponding direct connection 900 between the transceiver 810 and the decoder 630.The unit 740 may, of course, be adapted for receiving coded signals and decoding such signals as well. Hence, the unit 740 may include parts like the above described parts 620, 630, 820, 825, 830, 840 and 850. Likewise the unit 750 may be adapted to encode analogue signals in the manner described above. We claim: 1. A system for encoding a message, the message comprising a plurality of characters, each character having an occurrence probability; the method comprising the steps of: receiving a message; coding by the conversion unit (220, 650, 430 ,770, 820, 840) the received message by assigning code words (H), each having plural binary-valued digits, to the received characters (X) by transceivers (780,810) to a switch unit (310) as to generate a binary coded message by conversion unit (220, 650, 430, 770, 820, 840); 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 by compression module (270) having a first value ("1") than those assigned to characters of lower occurrence probability stored in the memory (440, 450, 420, 460, 700) characterized in that the coding consists of generating the binary coded by a transformation unit in a decoder (630) such that the number of bits in the coded message is minimized. 2. The encoding system as claimed in claim 1, wherein a number (r) based on a historical maximum number of mutually different characters is determined; selecting a suitable word length for the codewords (H) in response to the determined number (r) of mutually different characters (X). 3. The encoding system as claimed in claim 1 or 2, wherein a list of concordance between characters and codewords based on the occurrence probability of the characters in a received message by transceivers (780, 810) is generated and the number of bits having a first value ("1") in the codeword such that characters of higher occurrence probability are assigned codewords with fewer bits by a compression module (270) having the first value ("1") than those assigned to characters of lower occurrence probability stored in memory (420, 440, 450, 460, 700) and coding by conversion unit (220, 650, 430, 770, 820, 840) the received message by assigning code words (H) by a transformation unit in a decoder (630) to characters (X) in accordance with the list. 4. The encoding system as claimed in any of claims 1, 2 or 3, wherein the list is transmitted together with a signal indicating such transmission. 5. The encoding system as claimed in claim 3 or 4, wherein a new list of concordance between characters and code-words is established when the relative occurrence frequency of the characters in a received message deviates substantially from the relative occurrence frequency on which the present list of concordance was based. 6. The encoding system as claimed in any of claims 1 to 5, wherein the coding step is performed in accordance with a method comprising the steps of: receiving at least one message (S20, Fig 1A) comprising a plurality of characters (A,B,C); calculating, for each character, a value (p) indicating a relative frequency of the character in the at least one message (S40); assigning (S60) a first binary coded code symbol (Hi) to a character having the highest relative frequency (pi), the code symbol (Hi) comprising a plurality of binary digits; setting all or substantially all the binary digits in the first binary coded code symbol (Hi) to a second binary value ("0"); assigning a unique symbol (H2, Ha) to each unique remaining character in such a manner that the difference in Hamming weight is minimized between two symbols (Hi, H2) having the same relative frequency (pi, pa) or in between two symbols having proximal relative frequencies. 7. The encoding system as claimed in claims 3 to 6, wherein: a plurality of received messages form base for the list of concordance, the characters in said plurality of received messages constituting said historical maximum number of mutually different characters on which the word length for the codewords is based. 8. The encoding system as claimed in any of claims 3 to 7, wherein a new list of concordance between characters (X) and codewords (H) is established when a received message by transceiver (780, 810) comprises a higher number of mutually different characters than the present list of concordance. 9. The encoding system as claimed in any of claims 1 to 8, wherein said codewords (H) are provided sequentially as a set (Y) of binary digits, each said binary digit having a first value or a second value. 10. The encoding system as claimed in claim 1, wherein the message having a plurality of characters is determined by: quantising an analogue signal having an amplitude with a non-uniform probability density as falling within one of a plurality of signal level ranges, each signal level range corresponding to a character. 11. The encoding system as claimed in claim 10, wherein a number (r) of quantising signal levels based on a historical maximum amplitude is determined and a selected amplitude resolution; selecting a suitable word length for the codewords in response to the determined number (r) of quantising signal levels. 12. The encoding system claimed in claim 10 or 11, wherein a list of concordance between quantising signal ranges and codewords is generated; said list being based on the occurrence probability of the quantising signal ranges in a received analogue signal and the number of bits having a first value ("1") in the codeword such that quantising signal ranges of higher occurrence probability are assigned codewords with fewer bits having the first value ("1") than those assigned to quantising signal ranges of lower occurrence probability; and coding the received analogue signal by assigning code words (H) to quantising signal ranges in accordance with the list. 13. The encoding system as claimed in claim 12, wherein the list is transmitted together with a signal indicating such transmission. 14. The encoding system as claimed in claim 12 or 13, wherein a new list of concordance between quantising signal ranges and codewords is established when the relative occurrence frequency of the quantising signal ranges in a received analogue signal deviates substantially from the relative occurrence frequency on which the present list of concordance was based. 15. The encoding system as claimed in any of claims 10 to 14, wherein the coding step is performed in accordance with a method comprising the steps of: receiving an analogue signal during at least a predetermined time interval; determining a plurality of quantising amplitude level ranges; calculating, for each amplitude level range, a value (p) indicating a relative frequency of the amplitude level range in the analogue signal; assigning (S60) a first binary coded code symbol (Hi) to an amplitude level range having the highest relative frequency (pi), the code symbol (Hi) comprising a plurality of binary digits; all or substantially all the binary digits in the first binary coded code symbol (Hi) being set to a second binary value ("0"); assigning a unique symbol (Ha, Ha) to each remaining amplitude level range in such a manner that the difference in Hamming weight is minimized between two symbols (Hi, Ha) having the same relative frequency (pi, pa) or in between two symbols having proximal relative frequencies. 16. The encoding system as claimed in any of claims 10 to 15, wherein a word indicative of the determined number (r) of quantising signal ranges is delivered. 17. The encoding system as claimed in any of claims 10 to 16, wherein a word indicative of the historical maximum amplitude is delivered. 18. The encoding system as claimed in any of claims 12 to 17, wherein a new list of concordance between signal ranges are quantised and codewords (H) when a received signal comprises higher maximum amplitude than the maximum amplitude on which the present list of concordance was based. 19. The encoding system as claimed in any of claims 10 to 18, wherein said codewords (H) are provided sequentially as a first set (Y) of binary digits, each said binary digit having a first value or a second value. 20. The encoding system as claimed in 9 or 19, wherein encoding (S220 -S370, Fig 3b, 3C) the first set of digits (Y) is carried out such that a second set (E) of binary digits (ei, e;+ i) is generated; and selecting the digits (ei, ei+ i)in the second set (E) of digits such that the number of digits having the second binary value in the second set (E) is higher than the number of digits having the second binary value in the first set (Y). 21. The encoding system as claimed in claim 20, wherein the process of generating digits (ei) of the second set (E) of binary digits consists of setting the value of the m first digits (ei) of the second set (E) equal to the value of the m first digits (yi) in the first set (Y), where m is a positive integer. 22. The encoding system as claimed in claim 20 or 21, wherein the process of generating a next digit (e;+ i) in the second set of digits comprises the steps of: generating a prediction value (pi+i) in response to a number of previous digits (yi) in the first set of digits (Y); reading the value of an actual digit (yi+ i) in the first set of digits (Y); calculating (S300) the Hamming distance between the prediction value (pi+i) and value of the actual digit (yi+i); setting the value of the digit (ei-n) in the second set of digits (E) equal to the calculated Hamming distance value. 23. The encoding system claimed in claim 20, wherein the process of generating digits (ei) of the second set (E) of binary digits consists of setting the value of the m first digits (ei) of the second set (E) equal to the value of the m first digits (yi) in the first set (Y), where m is a positive integer generating a prediction value (pi+i) in response to a predefined number of previous digits (yi) in the first set of digits (Y); said predefined number being a positive integer equal to, or lower than, m; reading the value of an actual digit (y;+ i) in the first set of digits (Y); calculating (S300) the Hamming distance between the prediction value (p;+i) and value of the actual digit (yi+i); setting the value of the digit (e;+i) in the second set of digits (E) equal to the calculated Hamming distance value. 24. The encoding system as claimed in claim 22 or 23, wherein the process of generating a prediction value (pi+i) comprises the steps of: establishing (S230) a plurality of predictor count values (V), each predictor count value (V) being selectable (S240, S350) dependent on digits in the first set of digits (Y); initially setting all the predictor count values (V) to zero; and thereafter selecting a combination of digits (yi-ym) in the first set of digits; fl) selecting a predictor count value (V) in response to the selected combination of digits in the first set of digits (Y); f2) reading the selected predictor count value (V); f3) setting the prediction value (pi+i) to a first value if the selected predictor count value (V) is higher than a predetermined value (S260, S270), and setting the prediction value (pi+i) to a second value if the selected predictor count value (V) is lower than the predetermined value (S260, S280); f4) increasing (S320) the selected predictor count value (V) if (S310) the value of the actual digit (yi+i) in the first set of digits (Y) equals one, and decreasing (S330) the selected predictor count value (V) if (S310) the value of the actual digit (yi+i) in the first set of digits (Y) equals zero; f5) selecting a new combination of digits in the first set of digits (Y); repeating steps fl) to f5) until all digits (yi+i) in the first set of digits (Y) have been read. 25. The encoding system as claimed in any of claims 22 to 24, wherein the process of calculating (S300) the Hamming distance between the predicted value (pi+i) and value of the actual digit (yi+ij comprises the steps of: adding (S300) the predicted value (pi+i) and value of the actual digit (yi+i) modulo 2. 26. The system as claimed in any of claims 1 to 25, wherein the encoded message is compressed. 27. The system as claimed in any of claims 1 to 25, wherein the second set of digits (E) is encoded in accordance with Huffman Coding.

Full Text

The present invention relates to a system for encoding a message and apparatus for carrying out such method.
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.
US 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 US 5,062,152 each code word is predetermined to include eight binary-valued digits.
US 5,488,616 relates to an encoding method. According to US 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 C32 and a second code C34. In a final step one or both of the codes C32, C34 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 accor-dance with the occurrence probability of the characters and the number of bits hav-ing 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 em-
bodiment 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.
Brief description of the drawings
For simple understanding of the present invention, it will be described by means of examples and with reference to the accompanying drawings, of which:
Figure 1 A is a flow chart illustrating a method for creating a table of correspondence between characters in a human language message and code symbols.
Figure 1B is a representation of a transformation table.
Figure 2 is a flow chart illustrating a method for data compression according to one embodiment of the invention.
Figure 3 A illustrates a set of finite state machines, according to one embodiment of the invention.
Figure 3B and 3C is a flow chart illustrating in detail one of the steps in the flow chart according to Figure 2.
Figure 3D is an example of a transformation table for co-operation with the finite state machines according to Figure 3 A.
Figure 3E is an example of a bit stream.
Figure 4 shows a schematic block diagram of a first embodiment of a data compression device according to one embodiment of the invention.
Figure 5 is a schematic block diagram of an estimator for use in a data compression device according to Figure 4.
Figure 6 is a schematic block diagram of a portable electronic device comprising means for restoring information which has been compressed and stored according to the method described in relation to Figure 2.
Figure 7 shows a data restoring device according to one embodiment of the invention.
Figure 8 is a flow chart illustrating a method for decoding according to an embodiment of the invention.
Figure 9A and 9B is a flow chart illustrating in detail one of the steps in the flow chart according to Figure 8.
Figure 10 is a schematic block diagram of a communications system including units for coding and decoding an analogue signal.
Detailed description of embodiments
A human language comprises certain number of words, and some of these words are more frequently used than others. Each word can be represented by a specific combination of characters, or sometimes by only one character. This means that some characters are more frequently used than others in any one particular language. In electronic devices, such as mobile telephones, there are stored a certain number of predetermined messages, each of which is to be displayed on a display unit of the mobile telephone in response to a certain event. Commonly these messages are stored in a read-only memory. In order to display a message the corresponding data is read from the memory and for each character the corresponding ASCII-code is delivered to the display unit, which in response thereto displays a combination of ASCII-codes constituting the selected message.
As stated above, some characters have a higher relative frequency than others in one particular human language or in one particular predetermined set of messages. The present invention relates to a method for reducing the number of bits necessary for representing information in a predetermined language and/or for reducing the num-ber of bits necessary for representing a predetermined set of messages in any language.
A Method for Creating a Transformation Table
Figure 1A is a flow chart illustrating a method for obtaining a transformation table such that the character in a chosen set of messages, or the characters in a selected language, can be transformed into code symbols such that the total Hamming weight of messages of the selected type will be minimised.
A symbol may comprise one or a plurality of components. According to the preferred embodiment the each code symbol is a combination of binary digits.
The Hamming weight is minimised when the number of digits having value "1" is minimised. By transforming all the characters into corresponding Hamming symbols two important objects are achieved. The first object is that of assigning a weight to each character. As described below, a lower Hamming weight also leads to a larger compressibility of the symbol, thereby providing a link between the Hamming weight and the memory space required for storing the symbol. Secondly, the trans-formation into Hamming symbols in the manner described below reduces the weight difference between two consecutive characters in the message. In other words the number of digit positions which are different in a second symbol as compared to a first symbol is reduced.
With reference to Figure 1A a first step S10 is to select a human language. The se-lected human language could be for example English, French, Swedish or any other human language which uses characters for composing messages. A variable is assigned the name of the selected language, and this language identifying variable is saved for identifying the table to be created.
In step S20 a complete set of messages is received. The number of characters in a complete set of messages could be for example 2500. According to one embodiment of the invention each character is composed of 8 bits.
In step S30 the number of mutually different characters are counted and a variable r is assigned the count value. In a typical alphabet the number of mutually different characters may be for example 64.
In step S40 the relative frequency for each character is calculated, and in step S50 the characters are sorted in order of decreasing relative frequency. In other words the most commonly used character is placed first in the list and the most infrequent
character is placed last in the list. An example of such a list is shown in Figure IB. In Figure IB is shown a memory unit 10 having a plurality of memory positions 20. Each memory position may for example comprise 8 bits. The first memory position is provided with the language identifying variable, which may for example be the letter E identifying that the list/table comprises characters used in a set of English language messages. The second memory position in the list indicates the number of characters stored in this particular list. In this example the number of different char-acters is 64. The third memory position contains the ASCII-code for the character which has the highest relative frequency pi. hi this example the most frequent char-acter is "H". In the fourth memory position is stored the character (hi this example "G" having the second highest relative frequency p2. In this manner the 64 different characters are placed in the list such that the character having the lowest relative frequency P64 is placed in the last position in the list.
In step S60 a symbol having only zeros (0) is assigned to the character having the highest relative frequency pi. In the example shown in Figure 1B the selected set of messages contained only 64 different characters, and therefore the symbol to be as-signed to the first character is a symbol comprising six digits, all of which are zero. According to the invention there is created a list of symbols, herein referred to as Hamming symbols, of increasing Hamming weight. The Hamming symbols are as-signed to the characters in the list so that the character having the highest relative frequency p1 is assigned a Hamming symbol having a lowest Hamming weight. The character having the lowest relative frequency p64 is assigned a Hamming sym-bol having a Hamming weight which is not lower than any of the other Hamming symbols. However, with the knowledge that the first Hamming symbol is a symbol with six digits, all of which are zero it is possible to calculate the subsequent Hamming symbol having a weight which is at most one weight step higher. According to the invention, therefore, it is not necessary to actually store a complete list of Hamming symbols. Instead it is sufficient to identify how many digits there are to be in the Hamming symbols. Since the number of digits required in the Hamming symbols can be calculated having knowledge of the number of characters, it is only
necessary to have a predetermined manner of calculating subsequent Hamming symbols starting from a first Hamming symbol containing only zeros.
In step S70 a table of correspondence is created and the table is delivered to a mem-ory unit for storage, as will be described below. Since none of the Hamming sym-bols actually needs to be stored, the list of correspondence only needs to include a variable indicating the name of the list, a figure indicating the number of characters in the list and the characters in order of decreasing relative frequency. Using this minimum amount of information it is possible to calculate the value of each Ham-ming symbol to be assigned to each character, which is the only information neces-sary for creating a table of correspondence. Accordingly, since it is only necessary to store a list of characters and a control word (the figure indicating the number of characters) a very small amount of memory space is needed for the table of corre-spondence.
A method for transforming a message
Figure 2 is a flow chart illustrating a method for transforming a message into a bit stream, such that the bit stream has a minimal number of digits.
According to a first step S1 00 of an embodiment of the method, a message ML com-prising a plurality of characters X is transformed into a bit stream Y.. This is achieved by receiving the message ML (step S 110), and transforming each character X into a corresponding symbol H, using a table as described above in connection with Figures 1B and 1A. According to step S120 consecutive characters in the mes-sage are consecutively transformed into symbols such that a stream of symbols H is provided. According to the next step S130 of the method the generated symbols H are delivered as a bit stream.
According to step S140 the bit stream Y is provided to an estimator for transforming the received bit stream into a second bit stream E. The purpose of step S140 is to
provide a second bit stream E consisting mostly of zeros (0) in response to the bit stream produced by step S130. Another purpose of step S140 is to provide a second bit stream E whose digits are as close as possible to random variables which are in-dependently and identically distributed. Step S140 is described in more detail with reference to Figure 3 below.
According to step S150 the second bit stream produced in step S140 is compressed in accordance with a compression algorithm. According to one embodiment of the invention the compression algorithm used is Huffman coding. For detailed informa-tion about Huffman coding the reader is referred to D.A. Huffman. "A method for the construction of minimum redundancy codes." Proc. IRE, 40:1098-1101, 1952.
The compression step S150 generates a third bit stream C having fewer digits than the second bit stream. In fact the method as described above reduces a message ME in the English language to a mere 57.8% of the original number of bits. This figure was achieved for a full set of status messages for cellular phones, where the original messages in English required a size of 2323 bytes. The compression ratio of 0,578 includes the transformation table used for transforming the characters into corre-sponding Hamming symbols. This means that the actual compression ratio of the message, assuming the transformation table is available at the receiving end where the message is to be retrieved, is even better.
According to step S160 the third bit stream which is generated by step S150 is stored into a memory device. Alternatively the third bit stream provided by step S150 is delivered to an output for transmitting it to another electronic device.
According to the invention an advantageous compression ratio is achieved in the above manner. The above information transformation method is therefore suitable for transforming messages into compressed bit streams before storing the message in a memory device, since the transformed message requires substantially less memory space than the original message. In the table below are provided examples of text
messages in eleven different languages, and the corresponding compression ratio achieved when the message was compressed. The compression ratio is calculated as the size of the compressed message plus the size of the transformation table divided by the size of the original set of messages.

(Table Removed)
TABLE 1
It is clear from the above examples (see TABLE 1) that the compression ratio is nearly independent of the language used in the original message.
Step S140 is described in more detail with reference to Figures 3 A, 3B and 3C. Since the method described with reference to Figure 3B and 3C uses a set of finite state machines, an example of such a set of finite state machines is shown in Figure 3 A. For the purpose of executing the method according to step S140 in accordance with a preferred embodiment of the invention there is used a set of finite state ma-chines having k'2m different states.
According to a preferred embodiment the parameters k and m are chosen as follows: k = 6, and m = 10. Parameter k is chosen to 6 because there are not more than 26 characters in an alphabet usually used in the messages to be coded according to the preferred embodiment. The parameter m is selected sufficiently large to provide a sufficient "history" and small enough to avoid problems with poor statistics in each state. Another consideration for the choice of parameter m is to select it to a suitable value depending on the availability of memory for the counters producing the count values V, as described below with reference to Fig 5 and 3C.
For the purpose of illustrating the underlying principle of the method a set of finite state machines having only 3 22 states is shown in Figure 3 A. Thus the set of finite state machines shown in Figure 3 A is based on k = 3 and m = 2. The fact that m = 2 means that each state is defined by two digits, as illustrated in Figure 3 A. The set of finite state machines in Figure 3 A consists of three different finite state machines 110, 120 and 130 since k equals 3. Each of the circles shown in Figure 3 A illus-trates a state in the set of finite state machines 110, 120, 130, and according to the invention there is a count value V provided in each state in the set of finite state ma-chines. In this manner the set of finite state machines according to Figure 3 A has a total of 12 different count values, each of which will be individually controlled in accordance with the method which will be described below.
In the following example, it is assumed that a set of messages has been analysed, according to the method described in connection with Figure 1A, such that a table of correspondence between characters X and symbols H in accordance with Figure 3D has been established. In a real case the characters X would be shown in for ex-ample ASCII-codes, and the list of characters would be proceeded by a number in-dicating the number of characters in the list, but for sake of simplicity in this expla-nation the table of correspondence is shown as a direct table of correspondence between alphabetic characters and 3-digit Hamming codes. The list in Figure 3D shows eight characters hi order of decreasing relative frequency and corresponding Hamming symbols in order of increasing Hamming weight.
With reference to Figure 3B step S200 indicates the method step of receiving a mes-sage in the form of a sequential bit stream Y = y1, y2, y3,... yn such as the bit stream shown in Figure 3E. In the next step S210 the estimator produces output digits Cj, which for the first m digits equals the input digits yi. In step S220 the value i is set torn.
In the following step S230 a number, k, of finite state machines are set up. In other words, a set of finite state machines comprising k different finite state machines are defined. Each finite state machine comprises 2m states, and there is a count value V in each state. In step S230 all the count values V in the set of finite state machines are set to zero.
The finite state machines are ordered such that there are machines Ml M2,.. Mj ...Mk. With reference to step S240 in Figure 3B the following procedure will start from finite state machine Mj, where j= (m mod k)+l. In the selected finite state ma-chine, state S=(y1, y2, ... ym) is initially selected.
In the selected state, the value V is read (step S250), and thereafter (step S260) there is a check if the V>0. If V>0 a prediction value pi+1 is set to one (1), as indi-cated by box S270 in Fig 3B. If V With reference to Figure 3B and Figure 3E the next input digit yi+1 is read (step S290), and the output value ei+1 is calculated, in step S300), by adding yi+1 and pi+1 modulo 2. Hence, 1+1 modulo 2 equals zero, 1+0 modulo 2 equals 1, and 0+1 modulo 2 equals 1.
Next, in step S310, there is a check of the value of digit yi+1. If yi+1l the count value V, in the selected state in the selected finite state machine, is increased by 1, i.e. V :=V+1, as illustrated in box S320 in Fig 3C. If yi+1=0 the count value V, in
the selected state in the selected finite state machine, is decreased by 1, i.e. V :=V-1, as illustrated in box S330 in Fig 3C.
Thereafter, in step S340, the next finite state machine Mj+i is selected.
In the selected finite state machine: the state indicated by the value of digit yi+1 and the previous state (Step S350) is selected. This is done in the manner commonly used for changing from one state to another state within one finite state machine. For example, with reference to Fig 3 A, when starting from state "00" in the first finite state machine 110 and the digit yj+1 is a "1" state "01" is selected in the sec-ond finite state machine 120, in accordance with the invention. When the current state is state "01" in the second finite state machine 120 and the digit yi+1 is a "1" there will be a transition to state "11" in the third finite state machine 130. If the current finite state machine is the last (k:th) finite state machine then there will be a transition to a state in the first finite state machine in the same manner.
Thereafter the index value i is increased by one, as indicated by box S360. Thereaf-ter there is a control if any further bits remain in the received bit stream Y, as indi-cated by step S370 in Figure 3C, and if the answer is "yes" we proceed again with step S250, reading the count value V in the selected state of the selected finite state machine. If, on the other hand, this was the last bit in the message the procedure is ended.
A data compression device
With reference to Figure 4 there is shown a block diagram of a first embodiment of a data compression device 200. The data compression device comprises a character input 210 for receiving characters of a message to be transformed. The character in-put 210 is coupled to a conversion unit 220 by means of a data bus 230. The data bus is capable of transferring eight digit characters in parallel, in accordance to one
embodiment of the invention. According to another embodiment of the invention the digits in the received characters are delivered in series to the conversion unit 220. Also, a character to be received at the character input 210 may comprise another number of digits. The conversion unit is set up to convert the received characters into symbols having a low Hamming weight, in the manner described above with reference to steps S110 and S120 in Figure 2. The resulting symbol, which may comprise a lower number of digits than the corresponding character, is delivered from output 234 via a bus 240 to the input 242 of a symbol-to-bit-stream converter 250. The symbol-to-bit-stream converter 250 delivers, on its output 252 a bit stream with digits yi to an input 254 of an estimator unit 260. The purpose of the estimator unit 260 is to further reduce the number of digits having the value " 1" in the bit stream, while maintaining the information content in the message. The estimator unit 260 produces a bit stream E=e1en in response to reception of a bit stream Y=y1-yn, where n is the number of digits in the bit stream provided to the estimator unit 260. The bit stream E is delivered on an output 262 of the estimator unit 260. The bit stream E is delivered to a compression module 270 which is set up to reduce the number of digits in the bit stream while maintaining the information content in the message. The compression module operates in accordance with a compression algorithm, such as for example Huffman coding. According to a preferred embodi-ment a static Huffman code is used. Hence the compression module 270 produces a bit stream C=Ci-cr, where r With reference to Figure 5 the estimator unit 260 is described in more detail. The estimator unit 260 has a series input 300 for receiving the bit stream Y comprising the bits yi. The received bits yi are delivered to a switch unit 310 which is set up to
switch the first m digits directly to an output 320. The bit stream input 300 is also coupled to a first input 340 of a modulo 2 adder 350, and, via a delay unit 355, to a predictor unit 330. The delay unit 355 remembers one bit such that it delivers bit y; when receiving bit yi+1. The predictor unit 330 has an output which is coupled to a second input 360 of the adder 350. The adder 350 has an output which is coupled to the estimator unit output 320. The estimator 260 is thus set up to perform the method described above with reference to Figure 3B and 3C.
In the above described manner the predictor unit 330 is set up to make a prediction Pi+i of the value of the next bit yi+1. In other words the predictor unit 330 is set up to "guess" what value the bit yi+1 has, basing the "guess" pi+1 on the historical values yh for h The value Ci+1 represents the Hamming distance between the predicted bit value pi+1 and the actual bit value yi+1. Thus the Hamming distance ei+1 between two succes-sive bits is zero (0) if the predictor makes correct predictions. It is clear from the above, with reference to table 1, that the method according to the invention achieves very favourable compression ratios. One of the causes for this advantageous result is accurate predictions pi+1 in accordance with the described prediction method.
As described below, with reference to Fig 9, the decoding method is based on doing the same type of prediction, using the already decoded bit values y, as "history" for achieving a value pj+i representing a prediction of the next Hamming distance Ci+1. Since the predictive decoding method uses the same type of prediction as the pre-dictive coding does, the result of the decoding will be the correct bit stream Y .
An electronic data processing device
With reference to Figure 6 there is shown a data processing device 400 comprising a display unit 410 for the display of information such as text messages. The data processing device 400 comprises a non volatile memory 420, a microprocessor 430 and a read/write memory 440. The memory 420 has a first memory portion 450 wherein a computer program is stored for controlling the normal functions of the data processing device 400. The data processing device may be for example a port-able electronic device such as a mobile telephone. The memory 420 also has a sec-ond memory portion 460, where a program for coding and/or decoding messages is stored. In another embodiment the program for coding and/or decoding messages is stored on a separate non-volatile recording medium 462. The program may be stored in an executable manner or in a compressed state.
When, in the following, it is described that the microprocessor 430 performs a cer-tain function this is to be understood that the microprocessor performs a certain part of the program which is stored in the memory 450 or a certain part of the program which is stored on the recording medium 462.
The microprocessor 430 is coupled to the display unit 410 via a data bus 470. A user of the data processing device is provided with information messages by means of characters being displayed on the display 410. A particular message may be dis-played in response to a certain event, such as for example the microprocessor hav-ing determined that the battery voltage in the electronic device is lower than a certain value, which prompts the microprocessor to display the message "CHANGE BATTERY".
The microprocessor 430 is coupled to the memory 420 by means of a data bus 480, and to the read/write memory 440 by means of a data bus 490. The microprocessor 430 also communicates with a data port 500 by means of a data bus 510.
The methods described with reference to Figures 1A, IB, 2, 3A-3D can be per-formed by the microprocessor 430 by means of the microprocessor performing the program stored in the memory portion 460. In response to an instruction to create a table of correspondence, in accordance to the method described with reference to Figure 1A, the microprocessor is set up to wait for reception of a message on the data port 500 and as the message is received on the data port 500 the characters are temporarily stored in the read/write memory 440. When all the characters of the re-ceived message, or of the received set of messages, have been temporarily stored, the microprocessor is set up to count the number of different characters and to cal-culate the relative frequency for each character. Thereafter the microprocessor 430 is set up to assign code symbols to the different characters in the manner described above, such that a table of correspondence is created.
Alternatively the microprocessor is set up to receive a ready made table of corre-spondence via the data port 500 and to store that table of correspondence in the read/write memory 440. As described with reference to Figure IB the table of corre-spondence may be limited to a list starting with a number, and followed by the same number of characters.
Thereafter the microprocessor may respond to an instruction for transforming the received message, or the received set of messages, into a reduced digit bit stream E, in accordance with the method described above with reference to Figure 3B. When the message, or the set of messages, have been transformed into a bit stream this bit stream is stored in the memory 440. The microprocessor may of course be set up to store the bit stream E bit by bit or sorted in for example eight bit words, depending on the most efficient way of operating the memory which is used, or depending on other hardware considerations.
A data restoring device
With reference to Figure 7 a block diagram of a first embodiment of a data restoring device 600 is described. The data restoring device comprises an input 610 for re-ceiving a compressed bit stream C consisting of a number of digits cj. The input 610 is coupled to a decompression module 620, which is arranged to expand the bit stream C into a longer bit stream E while maintaining the information content. The decompression module 620 may be set up to perform decoding in accordance with a static Huffman code.
The decompression module 620 delivers the expanded bit stream E to an input 622 of a transformation unit 630 which is set up to perform substantially the reverse function of the estimator 260 which is described above. Hence the transformation unit 630 delivers a bit stream Y comprising a number of symbols H in series. For this purpose the estimator 260 includes a switch 632 functioning as switch 310 in fig 5. A delay unit 634 delivers bit y; on reception of bit yi+i, in analogy with unit 355 in fig 5, and a predictor unit 635 generates prediction values pi+1 in response to receiving the "historical" values y;. Whereas the predictor unit 330 in the encoder 260 is coupled in a feed-forward fashion, the predictor 635 in the decoder 630 is coupled in a feed-back fashion such that the output Y is used as "historical" data for decoding the input bit string E.
The transformation unit 630 is set up to deliver the bit stream Y to an output 638. A converter 640 is coupled to the output 638 for converting the bit stream to symbols. The symbols H are delivered, via a data bus, to an input 642 of a conversion unit 650. The conversion unit 650 operates to convert the symbols H into characters X, such that the original message is restored. The characters X are delivered from the conversion unit 650 to an output 660. The characters delivered on the port 660 may be for example eight bit ASCII-codes.

A method for restoring a message
Figure 8 is a flow chart illustrating a method for restoring a message M from a com-pressed bit stream C, in accordance with one embodiment of the invention. Accord-ing to a first step S600 a compressed bit stream C is received. The bit stream C is expanded into a bit stream E (step S610) using a known method for decod-ing/expanding, such as Huffman decoding. The bit stream E is then transformed into a bit stream Y, essentially by performing the method described with reference to Figures 3B and 3C in reverse (S620).
Thereafter the bit stream Y is transformed into characters X such that the original message M is restored (step S630). This is achieved by dividing the bit stream Y into symbols H (S640), and thereafter transforming each symbol H into a corre-sponding character X (step S650). The transformation of symbols H into characters X is performed using a table of correspondence which was also included in the compressed bit stream C. Alternatively the transformation table is already provided and the compressed bit stream C includes only information to be transformed into a message. According to a third embodiment of the symbol-to-character transforma-tion step, the compressed bit stream only comprises a number indicating the number of different characters in the message and a list of the characters. For the purpose of obtaining the transformation table a microprocessor, such as the microprocessor 430 (see Figure 6) may be set up to calculate the symbols H corresponding to each char-acter X in accordance with a predetermined algorithm which may be provided in the program stored in the memory portion 460 (Figure 6).
When the symbols H have been transformed into characters X the resulting message is delivered.
With reference to Figure 6 the compressed bit stream C may be provided in a mem-ory portion 700 in the non volatile memory 420. In response to a message presenta-tion instruction the microprocessor 430 may, using the program stored in the mem-

ory portion 450, use a standard expansion algorithm for decompressing a data re-storing program which was stored in a program portion 710 of the memory 450. The program code stored in memory portion 710 is thus expanded and positioned in a memory portion 720 of the memory 440. As mentioned above the memory 440 may be a random access memory RAM. The microprocessor thereafter continues by exe-cuting the data restoring program from the memory portion 720. The execution of ,the data restoring program includes the step of reading the compressed bit stream C from the memory portion 700 in the non volatile memory 420 and thereafter execut-ing the method steps S610, S620, S640 and S650 such that the compressed bit stream C is transformed into a stream of characters X constituting a message M. The message M, or parts of the message, are delivered by the microprocessor 430 to the display unit 410 via the data bus 470. Alternatively, depending on the circum-stances, the message M may be delivered to the data port 500 via the data bus 510.
With reference to Figures 9A and 9B there is described in detail how the transfor-mation of bit stream E into a bit stream Y (S620 in Figure 8) is performed. The method described with reference to Figures 9A and 9B is herein referred to as a predictive decoding method, and the method described above with reference to Fig-ures 3B and 3C is herein referred to as a predictive encoding method. The predictive decoding is performed essentially in the same manner as the predictive encoding, as is clear by comparing the flow chart according to Figure 9 with the flow chart ac-cording to Figures 3B and 3C. Thus the method steps S700 to S870 essentially cor-respond to the method steps S200 to S370 described above. The difference between the decoding and the encoding is essentially that whereas in the encoding method digit yi+1 is read from the input (S290) and the digit ei+1 is calculated, the opposite is true in the decoding method. With reference to Figure 9B the input digit ei+1 is read and the output digit yi+1 is calculated. Hence in step S810 in the decoding method the question about the value yi+i relates to the question of whether the output digit equals one or zero, whereas in the encoding method step S310 relates to the ques-tion of the value of the input value
With reference to Figure 6 the data restoring program in the memory portion 710 can be limited to a program routine defining the difference between the encoding and the decoding method. Thus there is a very small difference in the use of mem-ory space between on the one hand storing only the decoding program in the mem-ory and on the other hand storing the decoding program as well as the encoding program. Furthermore the skilled reader will realise that the above described coding methods and decoding methods require so advantageously few and mathematically uncomplicated steps that the program in itself will require an advantageously small amount of memory space. Hence a computer program for decoding and/or for en-coding messages according to the invention is particularly advantageous in portable electronic devices where the use of memory space for program code directly trans-lates into the size of the device. In mobile telephones, for example, a large number of messages need to be stored in the memory, and each telephone shall preferably be settable to produce the messages in a human language selected by the user. It is therefore an object of the present invention to provide a large number of such mes-sage sets in a small amount of memory space in a non volatile memory in the mobile telephone. Since the decoding program according to the invention requires such a small amount of memory space all the different language messages may be stored in a coded state, and when the user has selected the language in which he/she wants to see messages, the selected set of messages will be decoded in accordance with the above described method. A maximum amount of memory space is used during the execution of the predictive encoding and/or the predictive decoding program, since a number of count values V need to be temporarily stored during the execution of the program. Denoting the number of bits for each count value by c, the number of bits needed for storing the count values is k 2m c. According to the preferred em-bodiment the value of c may be selected to equal 2 or 3.
In the above described embodiments the Hamming weight of the message is de-creased for the purpose of providing an encoded message suitable for compression A suitable Huffman code provides a more efficient compression the lower the Hamming weight of the message to be compressed. However, by the choice of a dif-
ferent Huffman code a more efficient compression is achieved the higher the Hamming weight of the message to be compressed. Thus, according to the inven-tion, the transformation of characters into code symbols can be done in such a man-ner that the Hamming weight of the encoded message is maximised. In this case, the predictive encoding method is modified such that it strives to generate a bit stream E having a higher Hamming weight than the of the input bit stream Y.
A Communications Network
Figure 10 shows a communications network 735 including two units 740 and 750 communicating via a radio link. The unit 740 includes a microphone 760 for gen-erating an analogue signal, and a conversion unit 770 for quantising the analogue signal into a plurality of quantising ranges and assigning codewords H to the quan-tising ranges.
Hence, on receiving an analogue signal the conversion unit 770 delivers a sequence of codewords H in the form of a bitstream Y. According to a preferred embodiment the bitstream Y is delivered to an estimator unit 260, of the type described in detail above. The output E of the estimator unit is delivered to a compression module 270, also operating as described above. The compressed bit stream C delivered by the compression module 270 is delivered to a transceiver 780. The transceiver 780 in-cludes a communications port 790, e.g. an antenna, for communicating with the unit 750.
The unit 750 includes a communications port 800, e.g. an antenna, coupled to a transceiver 810 for receiving and delivering signals. The transceiver 810 is coupled to a decompression module 620 of the type described above, for translating a com-pressed bitstream C into a decompressed bitstream E. The decompressed bitstream E is delivered to a decoder 630 of the type described above in connection with Fig. 7. The output Y of the decoder 630 is delivered to a conversion unit 820.
The conversion unit 820 converts the received bitstream Y into an analogue signal, which is delivered e.g. to a loudspeaker 850.
The conversion unit 820 includes a controller 825 and a memory 830 in which con-version information including a conversion table is stored. The memory 830 holds information about the word length of the codewords H. Using that information, the received bitstream Y is divided into codewords H by the controller 825.
The codewords H are subsequently delivered to a digital-to-analogue (D/A) con-verter 840. The D/A converter 840 co-operates with the conversion table in the memory 830 to generate the signal levels defined by the codewords H. When the codewords H are fed to the D/A-converter 840 at the same frequency with which the original signal was sampled, the output of the D/A-converter will resemble the original analogue signal.
The function of the conversion unit 770 is as follows: The conversion unit 770 re-ceives an analogue signal having an amplitude with a non-uniform probability den-sity. The amplitude probability e.g. for speech has a maximum for zero amplitude, and decreases with increasing amplitude. Thus, after quantisation of a speech signal the most probable quantization level ranges are those corresponding to the lowest amplitudes. For the purpose of minimizing the Hamming weight of the A/D-converted signal Y, the codewords H should be selected to minimize the number of bits having value "1" (one). A coding scheme for assigning codewords, with a minimum of zeros, to an analogue signal is described in US 5,062,152, the content of which is hereby incorporated by reference.
Advantageously, the digital signal Y delivered by the conversion unit 770 can be minimized by adapting the word length of the codeword H to the required number r of quantising levels. If, for example, it is sufficient to have r=64 quantising levels the code symbols need only include six bits. If the number of quantising levels is
between 65 and 128, a word length of seven (7) bits is required. The number r of quantising levels definable by a word with d bits is: r = 2d
The necessary number of bits d hi the codeword H can therefore be established us-ing the following equation: d1 = ln(r)/ In2
If the result di is not an integer the number of bits d are established by rounding di up to the closest higher integer. If, for example, the required number of quantising levels is r = 190, the result d1= In(170)/ln2 = 7,409. Rounding d1 to the closest higher integer renders d=8. Hence, the required number of bits in the codewords H is d=8. The word length d of the codewords H is transmitted to the unit 750 and stored in memory 830. The variable d is used by controller 825 for dividing the bit-stream Y into codewords of the correct length upon reception of coded messages.
The required number of quantising signal ranges depends on the maximum ampli-tude of the analogue signal and of the amplitude resolution. For high fidelity repro-duction of the analogue signal the level ranges should be small so as to achieve a high amplitude resolution, hence a large number of quantising signal levels should be used.
For the purpose of establishing a maximum amplitude of the analogue signal the signal is measured for a certain time duration. The amplitude resolution can be set manually or automatically. By adapting the word length of the codewords to a his-torical maximum amplitude and a selected amplitude resolution the number of bits is minimized in the digital signal Y.
The conversion unit 770 generates a list of concordance between quantising signal ranges and codewords, i.e. a conversion table. The list is stored in a memory 860 co-operating with the conversion unit 770. The list stored in a memory 860 is used
for assigning code words H to quantising signal ranges in accordance with the es-tablished concordance.
Additionally the list of concordance and the word length d is delivered from con-version unit 770 to the transceiver 780 for transmission to the unit 750. On recep-tion of the list of concordance by transceiver 810, the list is delivered to conversion unit 820 for storage in the memory 830. The list stored in the memory 830 is there-after used by the D/A converter 840 for generating the signal levels defined by the codewords H
According to another embodiment of the communications network 735 the coded message, including the codewords H, is delivered directly from the conversion unit 770 to the transceiver 780, as indicated by dashed line 870 in Fig. 10. In that em-bodiment the receiving unit 750 also provides a direct connection 880 between the conversion unit 820 and the transceiver 810.
According to yet another embodiment of the communications network 735 the coded message including the codewords H is delivered directly from the conversion unit 770 to the compression module 270. The direct connection is obtained by a data bus, indicated by dashed line 882 in Fig 10. The unit 750 includes a corresponding data bus 884, providing a direct connection between the decompression module 620 and the conversion unit 820. The direct connection by data bus 884 enables a re-duction of the number of bits in the encoded message delivered by conversion unit 770.
According to yet another embodiment there is a direct connection 890 between the estimator unit 260 and the transceiver 780 thereby allowing transmission of the bit-stream E, which holds fewer zeros than the bitstream Y. Hence this embodiment has the advantage of further reducing the power required to transmit signals such as speech or music having non-uniform probability densities. The unit 750 includes a
corresponding direct connection 900 between the transceiver 810 and the decoder 630.The unit 740 may, of course, be adapted for receiving coded signals and decoding such signals as well. Hence, the unit 740 may include parts like the above described parts 620, 630, 820, 825, 830, 840 and 850. Likewise the unit 750 may be adapted to encode analogue signals in the manner described above.

We claim:
1. A system for encoding a message, the message comprising a
plurality of characters, each character having an occurrence probability;
the method comprising the steps of:
receiving a message;
coding by the conversion unit (220, 650, 430 ,770, 820, 840) the received message by assigning code words (H), each having plural binary-valued digits, to the received characters (X) by transceivers (780,810) to a switch unit (310) as to generate a binary coded message by conversion unit (220, 650, 430, 770, 820, 840); 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 by compression module (270) having a first value ("1") than those assigned to characters of lower occurrence probability stored in the memory (440, 450, 420, 460, 700) characterized in that the coding consists of generating the binary coded by a transformation unit in a decoder (630) such that the number of bits in the coded message is minimized.
2. The encoding system as claimed in claim 1, wherein a number (r)
based on a historical maximum number of mutually different characters
is determined;
selecting a suitable word length for the codewords (H) in response to the determined number (r) of mutually different characters (X).
3. The encoding system as claimed in claim 1 or 2, wherein a list of
concordance between characters and codewords based on the
occurrence probability of the characters in a received message by
transceivers (780, 810) is generated and the number of bits having a first
value ("1") in the codeword such that characters of higher occurrence
probability are assigned codewords with fewer bits by a compression
module (270) having the first value ("1") than those assigned to
characters of lower occurrence probability stored in memory (420, 440,
450, 460, 700) and coding by conversion unit (220, 650, 430, 770, 820,
840) the received message by assigning code words (H) by a
transformation unit in a decoder (630) to characters (X) in accordance
with the list.
4. The encoding system as claimed in any of claims 1, 2 or 3, wherein
the list is transmitted together with a signal indicating such
transmission.
5. The encoding system as claimed in claim 3 or 4, wherein a new list
of concordance between characters and code-words is established when
the relative occurrence frequency of the characters in a received message
deviates substantially from the relative occurrence frequency on which
the present list of concordance was based.
6. The encoding system as claimed in any of claims 1 to 5, wherein
the coding step is performed in accordance with a method comprising the
steps of: receiving at least one message (S20, Fig 1A) comprising a
plurality of characters (A,B,C); calculating, for each character, a value (p)
indicating a relative frequency of the character in the at least one
message (S40); assigning (S60) a first binary coded code symbol (Hi) to a
character having the highest relative frequency (pi), the code symbol (Hi)
comprising a plurality of binary digits; setting all or substantially all the
binary digits in the first binary coded code symbol (Hi) to a second binary value ("0"); assigning a unique symbol (H2, Ha) to each unique remaining character in such a manner that the difference in Hamming weight is minimized between two symbols (Hi, H2) having the same relative frequency (pi, pa) or in between two symbols having proximal relative frequencies.
7. The encoding system as claimed in claims 3 to 6, wherein: a
plurality of received messages form base for the list of concordance, the
characters in said plurality of received messages constituting said
historical maximum number of mutually different characters on which
the word length for the codewords is based.
8. The encoding system as claimed in any of claims 3 to 7, wherein a
new list of concordance between characters (X) and codewords (H) is
established when a received message by transceiver (780, 810) comprises
a higher number of mutually different characters than the present list of
concordance.
9. The encoding system as claimed in any of claims 1 to 8, wherein
said codewords (H) are provided sequentially as a set (Y) of binary digits,
each said binary digit having a first value or a second value.
10. The encoding system as claimed in claim 1, wherein the message
having a plurality of characters is determined by: quantising an analogue
signal having an amplitude with a non-uniform probability density as
falling within one of a plurality of signal level ranges, each signal level
range corresponding to a character.
11. The encoding system as claimed in claim 10, wherein a number
(r) of quantising signal levels based on a historical maximum
amplitude is determined and a selected amplitude resolution; selecting a suitable word length for the codewords in response to the determined number (r) of quantising signal levels.
12. The encoding system claimed in claim 10 or 11, wherein a list of
concordance between quantising signal ranges and codewords is
generated; said list being based on the occurrence probability of the
quantising signal ranges in a received analogue signal and the number of
bits having a first value ("1") in the codeword such that quantising signal
ranges of higher occurrence probability are assigned codewords with
fewer bits having the first value ("1") than those assigned to quantising
signal ranges of lower occurrence probability; and coding the received
analogue signal by assigning code words (H) to quantising signal ranges
in accordance with the list.
13. The encoding system as claimed in claim 12, wherein the list is
transmitted together with a signal indicating such transmission.
14. The encoding system as claimed in claim 12 or 13, wherein a new
list of concordance between quantising signal ranges and codewords is
established when the relative occurrence frequency of the quantising
signal ranges in a received analogue signal deviates substantially from
the relative occurrence frequency on which the present list of
concordance was based.
15. The encoding system as claimed in any of claims 10 to 14, wherein
the coding step is performed in accordance with a method comprising the
steps of: receiving an analogue signal during at least a predetermined
time interval; determining a plurality of quantising amplitude level
ranges; calculating, for each amplitude level range, a value (p) indicating
a relative frequency of the amplitude level range in the analogue signal;
assigning (S60) a first binary coded code symbol (Hi) to an amplitude level range having the highest relative frequency (pi), the code symbol (Hi) comprising a plurality of binary digits; all or substantially all the binary digits in the first binary coded code symbol (Hi) being set to a second binary value ("0"); assigning a unique symbol (Ha, Ha) to each remaining amplitude level range in such a manner that the difference in Hamming weight is minimized between two symbols (Hi, Ha) having the same relative frequency (pi, pa) or in between two symbols having proximal relative frequencies.
16. The encoding system as claimed in any of claims 10 to 15,
wherein a word indicative of the determined number (r) of quantising
signal ranges is delivered.
17. The encoding system as claimed in any of claims 10 to 16, wherein
a word indicative of the historical maximum amplitude is delivered.
18. The encoding system as claimed in any of claims 12 to 17, wherein
a new list of concordance between signal ranges are quantised and
codewords (H) when a received signal comprises higher maximum
amplitude than the maximum amplitude on which the present list of
concordance was based.
19. The encoding system as claimed in any of claims 10 to 18, wherein
said codewords (H) are provided sequentially as a first set (Y) of binary
digits, each said binary digit having a first value or a second value.
20. The encoding system as claimed in 9 or 19, wherein encoding
(S220 -S370, Fig 3b, 3C) the first set of digits (Y) is carried out such that
a second set (E) of binary digits (ei, e;+ i) is generated; and selecting the
digits (ei, ei+ i)in the second set (E) of digits such that the number of
digits having the second binary value in the second set (E) is higher than the number of digits having the second binary value in the first set (Y).
21. The encoding system as claimed in claim 20, wherein the process
of generating digits (ei) of the second set (E) of binary digits consists of
setting the value of the m first digits (ei) of the second set (E) equal to the
value of the m first digits (yi) in the first set (Y), where m is a positive
integer.
22. The encoding system as claimed in claim 20 or 21, wherein the
process of generating a next digit (e;+ i) in the second set of digits
comprises the steps of: generating a prediction value (pi+i) in response to
a number of previous digits (yi) in the first set of digits (Y); reading the
value of an actual digit (yi+ i) in the first set of digits (Y); calculating
(S300) the Hamming distance between the prediction value (pi+i) and
value of the actual digit (yi+i); setting the value of the digit (ei-n) in the
second set of digits (E) equal to the calculated Hamming distance value.
23. The encoding system claimed in claim 20, wherein the process
of generating digits (ei) of the second set (E) of binary digits consists of
setting the value of the m first digits (ei) of the second set (E) equal to the
value of the m first digits (yi) in the first set (Y), where m is a positive
integer generating a prediction value (pi+i) in response to a predefined
number of previous digits (yi) in the first set of digits (Y); said predefined
number being a positive integer equal to, or lower than, m; reading the
value of an actual digit (y;+ i) in the first set of digits (Y); calculating
(S300) the Hamming distance between the prediction value (p;+i) and
value of the actual digit (yi+i); setting the value of the digit (e;+i) in the
second set of digits (E) equal to the calculated Hamming distance value.
24. The encoding system as claimed in claim 22 or 23, wherein the
process of generating a prediction value (pi+i) comprises the steps of:
establishing (S230) a plurality of predictor count values (V), each
predictor count value (V) being selectable (S240, S350) dependent on
digits in the first set of digits (Y); initially setting all the predictor
count values (V) to zero; and thereafter selecting a combination of digits
(yi-ym) in the first set of digits; fl) selecting a predictor count value (V) in
response to the selected combination of digits in the first set of digits (Y);
f2) reading the selected predictor count value (V); f3) setting the
prediction value (pi+i) to a first value if the selected predictor count value
(V) is higher than a predetermined value (S260, S270), and setting the
prediction value (pi+i) to a second value if the selected predictor count
value (V) is lower than the predetermined value (S260, S280); f4)
increasing (S320) the selected predictor count value (V) if (S310) the
value of the actual digit (yi+i) in the first set of digits (Y) equals one, and
decreasing (S330) the selected predictor count value (V) if (S310) the
value of the actual digit (yi+i) in the first set of digits (Y) equals zero; f5)
selecting a new combination of digits in the first set of digits (Y);
repeating steps fl) to f5) until all digits (yi+i) in the first set of digits (Y)
have been read.
25. The encoding system as claimed in any of claims 22 to 24,
wherein the process of calculating (S300) the Hamming distance
between the predicted value (pi+i) and value of the actual digit (yi+ij
comprises the steps of: adding (S300) the predicted value (pi+i) and
value of the actual digit (yi+i) modulo 2.
26. The system as claimed in any of claims 1 to 25, wherein the
encoded message is compressed.
27. The system as claimed in any of claims 1 to 25, wherein the second set of digits (E) is encoded in accordance with Huffman Coding.

Documents:

3812-del-1997-abstract.pdf

3812-del-1997-claims.pdf

3812-DEL-1997-Correspondence Others-(24-03-2011).pdf

3812-del-1997-correspondence-others.pdf

3812-del-1997-correspondence-po.pdf

3812-del-1997-description (complete).pdf

3812-del-1997-drawings.pdf

3812-del-1997-form-1.pdf

3812-del-1997-form-13.pdf

3812-del-1997-form-19.pdf

3812-del-1997-form-2.pdf

3812-DEL-1997-Form-27-(24-03-2011).pdf

3812-del-1997-form-3.pdf

3812-del-1997-form-4.pdf

3812-del-1997-form-6.pdf

3812-del-1997-gpa.pdf

3812-del-1997-petition-137.pdf

3812-del-1997-petition-138.pdf

abstract.jpg

« Previous Patent

Next Patent »

Patent Number

215563

Indian Patent Application Number

3812/DEL/1997

PG Journal Number

11/2008

Publication Date

14-Mar-2008

Grant Date

27-Feb-2008

Date of Filing

29-Dec-1997

Name of Patentee

TELEFONAKTIEBOLAGET LM ERICSSON (PUBL)

Applicant Address

S-126 25 STOCKHOLM, SWEDEN.

Inventors:

#	Inventor's Name	Inventor's Address
1	BERNARD JAN MARIE SMEETS	DALBACKAVAGEN 11, S-240 10 DALBY, SWEDEN.
2	JAN ABERG	SPOLEGATAN 8, S-22220 LUND, SWEDEN.

PCT International Classification Number

H03M 7/40

PCT International Application Number

N/A

PCT International Filing date

PCT Conventions:

#	PCT Application Number	Date of Convention	Priority Country
1	9604834-3	1996-12-30	Sweden