Reduced table size forward error correcting encoder

Details Reduced table size forward error correcting encoder Reduced table size forward error correcting encoder

2000-03-03

2004-07-20

Baker, Stephen M. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

Reexamination Certificate

active

06766490

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of data processing systems. Specifically, the present invention relates to a method and system for encoding information in a portable computer system.
2. Related Art
As the components required to build a computer system have reduced in size, new categories of computer systems have emerged. One of the more recent categories of computer systems is the “palmtop” computer system. A palmtop computer system is a computer that is small enough to be held in the hand of a user and is thus “palm-sized.”
Because palmtop computer systems are very small, full-sized keyboards are generally not efficient input devices. Instead of a keyboard device, some palmtop computers utilize a touch screen and display an image of a small keyboard thereon. When a particular button is pressed or tapped, a small keyboard image is displayed on the display screen. The user then interacts with the on-screen small keyboard image to enter characters, usually one character at a time. To interact with the displayed keyboard image (e.g., “virtual keyboard”), the user taps the screen location of a character with a pen. That corresponding character is then recognized and added to a data entry field, also displayed on the screen. However, for experienced users, the virtual keyboard input system can be a tedious input process.
Instead of using a keyboard device or a displayed keyboard, many palmtop computers employ a stylus and a digitizer pad as an input system. The pen and digitizer pad combination works well for palmtop computers because the arrangement allows a user to hold the palmtop computer system in one hand while scribing with the stylus onto the digitizer pad with the other hand. Most of these stylus-based palmtop computer systems provide some type of handwriting recognition system.
In addition to using keyboards, virtual keyboards and the digitizer, it has also proven convenient to exchange data between a computer system and a palmtop computer using a communication interface, such as a serial or parallel input port. Many palmtop computers also include an infrared communication port for transmitting data over a wireless link. Other palmtop computers further include a radio receiver/transmitter for transmitting data over a wireless link.
All communication circuits introduce some noise and interference into a signal, whether the signal is analog or digital. In addition, signals are distorted along their transmission path by noise and interference. The noise and interference add elements (errors) to the signals that need to be considered in order to recover the original signal.
Error correcting codes are known in the art and are used to encode and decode a signal in such a way that noise and interference errors can be detected and corrected by examination of the encoded data on the receiving end. In a forward error correcting code, extra (redundant) bits (“parity bits”) are added into a stream of data that is to be transmitted to another device. The parity bits are used by the receiving device to detect and correct errors in the received data.
In a block error correcting code, a block of K digits (e.g., a data word) is encoded using a code word of N digits (where N>K). For each sequence of K digits, there is a distinct code word of N digits. The code word is comprised of K data bits and N-K parity bits. Generally, such a code is known as a (N,K) code; certain types of these codes are also called Hamming codes. A total of 2
K
code words having N digits each is required for 2
K
data words. Thus, for example, for a data word that is eight (8) bits in length, 256 code words are required.
A typical encoding scheme of the prior art is generalized as mapping K-bit vectors X into N-bit vectors Y using a generator G specific to the code being used, in which:
[Y]=[X][G].
Thus, for example, if K=8 and N=12, then:
[Y
1
Y
2
Y
3
Y
4
Y
5
Y
6
Y
7
Y
8
Y
9
Y
10
Y
11
Y
12
]=[X
1
X
2
X
3
X
4
X
5
X
6
X
7
X
8
][G].
In this example, [Y] would have 8 data bits (X) and 4 parity bits (P):
[Y]=[X
1
X
2
X
3
X
4
X
5
X
6
X
7
X
8
P
1
P
2
P
3
P
4
].
Once G has been selected, the encoding scheme can be executed in advance for each possible combination of K bits, and the encoded results stored in a lookup table. Accordingly, to encode a K-bit data word, the data word is used as an index into the lookup table to identify the corresponding N-bit code word previously determined using generator G. For K=8 and N=12, for example, the lookup table will have 256 12-bit entries. Table 1 below is an example of such a lookup table.
TABLE 1
Example Prior Art Code Word Lookup Table (K = 8, N = 12)
CodeBook ($ indicates hexadecimal data):
$0000,
$0015,
$0026,
$0033,
$0049,
$005C,
$006F,
$007A
$008A,
$009F,
$00AC,
$00B9,
$00C3,
$00D6,
$00E5,
$00F0
$0107,
$0112,
$0121,
$0134,
$014E,
$015B,
$0168,
$017D
$018D,
$0198,
$01AB,
$01BE,
$01C4,
$01D1,
$01E2,
$01F7
$020B,
$021E,
$022D,
$0238,
$0242,
$0257,
$0264,
$0271
$0281,
$0294,
$02A7,
$02B2,
$02C8,
$02DD,
$02EE,
$02FB
$030C,
$0319,
$032A,
$033F,
$0345,
$0350,
$0363,
$0376
$0386,
$0393,
$03A0,
$03B5,
$03CF,
$03DA,
$03E9,
$03FC
$040D,
$0418,
$042B,
$043E,
$0444,
$0451,
$0462,
$0477
$0487,
$0492,
$04A1,
$04B4,
$04CE,
$04DB,
$04E8,
$04FD
$050A,
$051F,
$052C,
$0539,
$0543,
$0556,
$0565,
$0570
$0580,
$0595,
$05A6,
$05B3,
$05C9,
$05DC,
$05EF,
$05FA
$0606,
$0613,
$0620,
$0635,
$064F,
$065A,
$0669,
$067C
$068C,
$0699,
$06AA,
$06BF,
$06C5,
$06D0,
$06E3,
$06F6
$0701,
$0714,
$0727,
$0732,
$0748,
$075D,
$076E,
$077B
$078B,
$079E,
$07AD,
$07B8,
$07C2,
$07D7,
$07E4,
$07F1
$080E,
$081B,
$0828,
$083D,
$0847,
$0852,
$0861,
$0874
$0884,
$0891,
$08A2,
$08B7,
$08CD,
$08D8,
$08EB,
$08FE
$0909,
$091C,
$092F,
$093A,
$0940,
$0955,
$0966,
$0973
$0983,
$0996,
$09A5,
$09B0,
$09CA,
$09DF,
$09EC,
$09F9
$0A05,
$0A10,
$0A23,
$0A36,
$0A4C,
$0A59,
$0A6A,
$0A7F
$0A8F,
$0A9A,
$0AA9,
$0ABC,
$0AC6,
$0AD3,
$0AE0,
$0AF5
$0B02,
$0B17,
$0B24,
$0B31,
$0B4B,
$0B5E,
$0B6D,
$0B78
$0B88,
$0B9D,
$0BAE,
$0BBB,
$0BC1,
$0BD4,
$0BE7,
$0BF2
$0C03,
$0C16,
$0C25,
$0C30,
$0C4A,
$0C5F,
$0C6C,
$0C79
$0C89,
$0C9C,
$0CAF,
$0CBA,
$0CC0,
$0CD5,
$0CE6,
$0CF3
$0D04,
$0D11,
$0D22,
$0D37,
$0D4D,
$0D58,
$0D6B,
$0D7E
$0D8E,
$0D9B,
$0DA8,
$0DBD,
$0DC7,
$0DD2,
$0DE1,
$0DF4
$0E08,
$0E1D,
$0E2E,
$0E3B,
$0E41,
$0E54,
$0E67,
$0E72
$0E82,
$0E97,
$0EA4,
$0EB1,
$0ECB,
$0EDE,
$0EED,
$0EF8
$0F0F,
$0F1A,
$0F29,
$0F3C,
$0F46,
$0F53,
$0F60,
$0F75
$0F85,
$0F90,
$0FA3,
$0FB6,
$0FCC,
$0FD9,
$0FEA,
$0FFF
A problem with this prior art approach is that the lookup tables are large in size and therefore require a large amount of memory. For longer data words and/or code words, this problem is made even worse. For example, increasing the size of the data word by one bit (from 8 bits to 9) doubles the number of entries required in the lookup table, from 256 entries to 512; each additional bit in the data word doubles the size of the lookup table.
In a palmtop computer system, the amount of memory space is limited relative to desktop computer systems (e.g., personal computers), and therefore memory space is invaluable and needs to be efficiently used. In addition, it may take longer to complete the encoding and decoding processes using large lookup tables.
Consumer preferences are for palmtops and other such devices to be as small, light and fast as possible. As such, it is desirable to use the memory space available, as well as to perform necessary functions such as encoding and decoding, as efficiently as possible.
SUMMARY OF THE INVENTION
Accordingly, what is needed is a system or method for efficiently encoding and decoding a digital data stream in accordance with the limited resources available in palmtop computer systems and other small, low-power devices. In particular, what is needed is a system or method that satisfies the above need and that does not consume a large amount of the available memory space in such devices. The present invention pro

Affiliated with

Also associated with

Rating

Reduced table size forward error correcting encoder does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Reduced table size forward error correcting encoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reduced table size forward error correcting encoder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3197047