US 6,766,490 B1Grant
Reduced table size forward error correcting encoder
Issue Date:2004-07-20
•8 Claims
•12 Drawing Sheets
Abstract
A method and system for encoding and decoding a sequence of K binary digits using reduced-size lookup tables. The sequence of K binary digits is separated into multiple segments (e.g., a first segment and a second segment). The first segment is used as an index into a first lookup table that contains an encoded version of all combinations of binary digits possible in the first segment. In a similar manner, the second segment is used as an index into a second lookup table that contains an encoded version of all combinations of binary digits possible in the second segment. Using the first lookup table, an encoded sequence is obtained for the first segment, and an encoded sequence is obtained for the second segment using the second lookup table. An encoded sequence for the entire sequence of K binary digits is obtained by combining the encoded sequences for the first and second segments. Two lookup tables are thus used to encode the sequence of K binary digits instead of a single lookup table having 2Kentries. The sizes of the two lookup tables are such that, if combined, they would contain fewer than 2Kentries, thereby saving memory space in devices with limited memory capacity.
Metadata
Assignee
- palmOne, Inc.
Inventors
- Gary Garrabrant
- Katherine Elliott
Application Information
Application Number:US 09/518,581
Filing Date:2000-03-03
Priority Date:2000-03-03
Art Unit:7
Classifications
IPC:
H03M 1315
Field of Search:
714757714759714807
Patent Drawings (12 sheets)
Description
BACKGROUND OF THE INVENTION
[0002] 1. Field of the Invention
[0003] 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.
[0004] 2. Related Art
[0005] 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.”
[0006] 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.
[0007] 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.
[0008] 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.
[0009] 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.
[0010] 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.
[0011] 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 2Kcode words having N digits each is required for 2Kdata words. Thus, for example, for a data word that is eight (8) bits in length, 256 code words are required.
[0012] 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:
[0013] [Y]=[X][G].
[0014] Thus, for example, if K=8 and N=12, then:
[0015] [Y1Y2Y3Y4Y5Y6Y7Y8Y9Y10Y11Y12]=[X1X2X3X4X5X6X7X8][G].
[0016] In this example, [Y] would have 8 data bits (X) and 4 parity bits (P):
[0017] [Y]=[X1X2X3X4X5X6X7X8P1P2P3P4].
[0018] 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) |
[0019] 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.
[0020] 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.
[0021] 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
[0022] 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 provides these advantages and others not specifically mentioned above but described in the sections to follow.
[0023] A method and system are described for encoding and decoding a sequence of K binary digits using reduced-size lookup tables. In the present embodiment, the sequence of K binary digits is separated into multiple segments (for example, a first segment and a second segment), The first segment is used as an index into a first lookup table that contains an encoded sequence corresponding to each of the possible combinations of binary digits in the first segment. Similarly, the second segment is used as an index into a second lookup table that contains an encoded sequence corresponding to each of the possible combinations of binary digits in the second segment. Using the first lookup table, an encoded sequence is obtained for the first segment, and an encoded sequence is obtained for the second segment using the second lookup table. An encoded sequence for the entire sequence of K binary digits is obtained by combining the encoded sequences for the first and second segments.
[0024] In other embodiments, the K binary digits are separated into more than two segments. Accordingly, in these embodiments, more than two lookup tables are used to encode the K binary digits in a manner similar to that just described.
[0025] Hence, in accordance with the present invention, instead of a single lookup table with 2Kentries, multiple reduced-size lookup tables are used to encode a sequence of K binary digits. The total number of entries in the reduced-size lookup tables is less than 2Kentries, thereby saving memory space in devices with limited memory capacity, such as palmtop computers.
[0026] In the present embodiment, an error correcting code is used to generate the encoded sequences that are stored in the reduced-size lookup tables. In one embodiment, the error correcting code is a Hamming code.
[0027] In one embodiment, the encoded sequences for the first and second segments are combined using a binary add XOR (exclusive or) operation.
[0028] In another embodiment, the sequence of K binary digits to be encoded are substantially compliant with the Mobitex standard.
BRIEF DESCRIPTION OF THE DRAWINGS
[0029] FIG. 1 is a block diagram of an exemplary network environment including a palmtop computer system in accordance with one embodiment of the present invention.
[0030] FIG. 2 is a top side perspective view of a palmtop computer system in accordance with one embodiment of the present invention.
[0031] FIG. 3 is a bottom side perspective view of the palmtop computer system of FIG. 2.
[0032] FIG. 4 is an exploded view of the components of the palmtop computer system of FIG. 2.
[0033] FIG. 5 is a block diagram of one embodiment of a palmtop computer system in accordance with the present invention.
[0034] FIG. 6A is a flowchart of the steps in a process for transmitting data in accordance with one embodiment of the present invention.
[0035] FIG. 6B is a flowchart of the steps in a process for receiving data in accordance with one embodiment of the present invention.
[0036] FIG. 7A is a flowchart of the steps in a process for encoding a sequence of data bits using reduced-size lookup tables in accordance with an embodiment of the present invention.
[0037] FIG. 7B is a flowchart of the steps in a process for encoding a sequence of bits using reduced-size lookup tables in accordance with another embodiment of the present invention.
[0038] FIGS. 8A and 8B illustrate example cases in which a sequence of bits are encoded using reduced-size lookup tables in accordance with an embodiment of the present invention.
[0039] FIG. 9 illustrates an example case in which reduced-size lookup tables are used to decode a sequence of bits in accordance with one embodiment of the present invention.
DETAILED DESCRIPTION OF THE INVENTION
[0040] In the following detailed description of the present invention, numerous specific details are set forth in order to provide a thorough understanding of the present invention. However, it will be recognized by one skilled in the art that the present invention may be practiced without these specific details or with equivalents thereof. In other instances, well known methods, procedures, components, and circuits have not been described in detail as not to unnecessarily obscure aspects of the present invention.
Notation and Nomenclature
[0041] Some portions of the detailed descriptions which follow are presented in terms of procedures, steps, logic blocks, processing, and other symbolic representations of operations on data bits that can be performed on computer memory. These descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. A procedure, computer executed step, logic block, process, etc., is here, and generally, conceived to be a self-consistent sequence of steps or instructions leading to a desired result. The steps are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated in a computer system. It has proven convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, or the like.
[0042] It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise as apparent from the following discussions, it is appreciated that throughout the present invention, discussions utilizing terms such as “separating” or “indexing” or “forming” or “generating” or “storing” or “using” or “combining” or “adding” or the like, refer to the action and processes of a computer system (e.g., processes 600, 665, 700 and 750 of FIGS. 6A, 6B, 7A and 7B, respectively), or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within the computer system's registers and memories into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices.
Exemplary Palmtop Platform
[0043] FIG. 1 is a block diagram of an exemplary network environment 50 including a portable computer system 100 in accordance with one embodiment of the present invention. Portable computer system 100 is also known as a palmtop or palm-sized computer system. Portable computer system 100 has the ability to transmit and receive data and information over a wireless communication interface (e.g., a radio interface).
[0044] In the present embodiment, base station 32 is both a transmitter and receiver base station which can be implemented by coupling it into an existing public telephone network 34. Implemented in this manner, base station 32 enables portable computer system 100 to communicate with a proxy server computer system 36, which is coupled by wire to the existing public telephone network 34. Furthermore, proxy server computer system 36 is coupled to the Internet 52, thereby enabling portable computer system 100 to communicate with the Internet 52. It should be appreciated that within the present embodiment, one of the functions of proxy server 36 is to perform operations over the Internet 52 on behalf of portable computer system 100. For example, proxy server 36 has a particular Internet address and acts as a proxy device for portable computer system 100 over the Internet 52. It should be further appreciated that other embodiments of a communications network may be utilized in accordance with the present invention.
[0045] The data and information which are communicated between base station 32 and portable computer system 100 are the same type of information and data that can conventionally be transferred and received over a public telephone wire network system. However, a wireless communication interface is utilized to communicate data and information between portable computer system 100 and base station 32. It should be appreciated that one embodiment of a wireless communication system in accordance with the present invention is the Mobitex wireless communication system.
[0046] FIG. 2 is a perspective illustration of the top face 100aof one embodiment of the palmtop computer system 100 of the present invention. The top face 100acontains a display screen 105 surrounded by a bezel or cover. A removable stylus 80 is also shown. The display screen 105 is a touch screen able to register contact between the screen and the tip of the stylus 80. The stylus 80 can be of any material to make contact with the screen 105. The top face 100aalso contains one or more dedicated and/or programmable buttons 75 for selecting information and causing the computer system to implement functions. The on/off button 95 is also shown.
[0047] FIG. 2 also illustrates a handwriting recognition pad or “digitizer” containing two regions 106aand 106b. Region 106ais for the drawing of alphabetic characters therein (and not for numeric characters) for automatic recognition, and region 106bis for the drawing of numeric characters therein (and not for alphabetic characters) for automatic recognition. The stylus 80 is used for stroking a character within one of the regions 106aand 106b. The stroke information is then fed to an internal processor for automatic character recognition. Once characters are recognized, they are typically displayed on the screen 105 for verification and/or modification.
[0048] FIG. 3 illustrates the bottom side 100bof one embodiment of the palmtop computer system that can be used in accordance with various embodiments of the present invention. An extendible antenna 85 is shown, and also a battery storage compartment door 90 is shown. A communication interface 180 is also shown. In one embodiment of the present invention, the communication interface 180 is a serial communication port, but could also alternatively be of any of a number of well-known communication standards and protocols, e.g., parallel, SCSI (small computer system interface), Firewire (IEEE 1394), Ethernet, etc.
[0049] FIG. 4 is an exploded view of the palmtop computer system 100 in accordance with one implementation. Computer system 100 contains a front cover 210 having an outline of region 106 and holes 75afor receiving buttons 75b. A flat panel display 105 (both liquid crystal display and touch screen) fits into front cover 210. Any of a number of display technologies can be used, e.g., liquid crystal display (LCD), field emission display (FED), plasma, etc., for the flat panel display 105. A battery 215 provides electrical power. A contrast adjustment (potentiometer) 220 is also shown. On/off button 95 is shown along with an infrared emitter and detector device 64. A flex circuit 230 is shown along with a personal computer (PC) board 225 containing electronics and logic (e.g., memory, communication bus, processor, etc.) for implementing computer system functionality. The digitizer pad is also included in PC board 225. A midframe 235 is shown along with stylus 80. Position-adjustable antenna 85 is shown.
[0050] A signal (e.g., radio) receiver/transmitter device 108 is also shown between the midframe and the rear cover 245 of FIG. 4. The receiver/transmitter device 108 is coupled to the antenna 85 and also coupled to communicate with the PC board 225. In one implementation the Mobitex wireless communication system is used to provide two-way communication between computer system 100 and other networked computers and/or the Internet via a proxy server (see FIG. 1).
[0051] FIG. 5 illustrates circuitry of computer system 100, some of which can be implemented on PC board 225 (FIG. 4). Computer system 100 includes an address/data bus 110 for communicating information, a central processor 101 coupled with the bus for processing information and instructions, a volatile memory 102 (e.g., random access memory, RAM) coupled with the bus 110 for storing information and instructions for the central processor 101 and a non-volatile memory 103 (e.g., read only memory, ROM) coupled with the bus 110 for storing static information and instructions for the processor 101. Computer system 100 also includes an optional data storage device 104 (e.g., memory stick) coupled with the bus 110 for storing information and instructions. Device 104 can be removable. As described above, computer system 100 also contains a display device 105 coupled to the bus 110 for displaying information to the computer user. PC board 225 can contain the processor 101, the bus 110, the ROM 103 and the RAM 102.
[0052] With reference still to FIG. 5, computer system 100 also includes a signal transmitter/receiver device 108 which is coupled to bus 110 for providing a physical communication link between computer system 100 and a network environment (e.g., network environment 50 of FIG. 1). As such, signal transmitter/receiver device 108 enables central processor unit 101 to communicate wirelessly with other electronic systems coupled to the network. It should be appreciated that within the present embodiment, signal transmitter/receiver device 108 is coupled to antenna 85 (FIG. 4) and provides the functionality to transmit and receive information over a wireless communication interface. It should be further appreciated that the present embodiment of signal transmitter/receiver device 108 is well-suited to be implemented in a wide variety of ways. For example, signal transmitter/receiver device 108 could be implemented as a modem.
[0053] In one embodiment, computer system 100 includes a communication circuit 109 coupled to bus 110. Communication circuit 109 includes an optional digital signal processor (DSP) 120 for processing data to be transmitted or data that are received via signal transmitter/receiver device 108. Additional information regarding the functions of communication circuit 109 are provided in conjunction with FIGS. 6A and 6B. Alternatively, some or all of the functions performed by DSP 120 can be performed by processor 101.
[0054] Also included in computer system 100 of FIG. 5 is an optional alphanumeric input device 106 which in one implementation is a handwriting recognition pad (“digitizer”) having regions 106aand 106b(FIG. 2), for instance. Alphanumeric input device 106 can communicate information and command selections to processor 101. Computer system 100 also includes an optional cursor control or directing device (on-screen cursor control 107) coupled to bus 110 for communicating user input information and command selections to processor 101. In one implementation, on-screen cursor control device 107 is a touch screen device incorporated with display device 105. On-screen cursor control device 107 is capable of registering a position on display device 105 where the stylus makes contact. The display device 105 utilized with computer system 100 may be a liquid crystal display device, a cathode ray tube (CRT), a field emission display device (also called a flat panel CRT) or other display device suitable for creating graphic images and alphanumeric characters recognizable to the user. In the preferred embodiment, display device 105 is a flat panel display.
Processes for Transmitting and Receiving Data
[0055] FIG. 6A is a flowchart of the steps in a process 600 for encoding data to be transmitted over a wireless link from a palmtop computer system (e.g., computer system 100 of FIG. 1) in accordance with one embodiment of the present invention. In one embodiment, process 600 is implemented by communication circuit 109 (specifically, DSP 120) of FIG. 5. In another embodiment, process 600 is implemented using processor 101 (FIG. 5) in lieu of DSP 120.
[0056] In step 610 of FIG. 6A, the data to be transmitted are received into process 600 from the host (e.g., from computer system 100 memory). In step 620 of FIG. 6A, a procedure for generating bit values for the cyclic redundancy check (CRC) is implemented.
[0057] In step 630, in the present embodiment, the data are encoded using an error correcting code. In one embodiment, a forward error correcting (FEC) code, such as a Hamming code, is used. In accordance with the present invention, the FEC encoding is performed using reduced-size lookup tables which are memory efficient. The reduced-size lookup tables occupy less space in memory than a single full-sized lookup table, and therefore are advantageously used in devices with limited memory space such as palmtop computers. Additional information regarding the use of reduced-size lookup tables in accordance with the present invention is provided in conjunction with FIGS. 7A, 7B, 8A and 8B.
[0058] In step 640, pseudonoise (PN) encoding of the data is performed. In step 650, the encoded data bits are converted to samples (e.g., audio samples, although other types of data may be used). In step 660, the samples are sent to a digital-to-analog converter (DAC). The encoded signals are then transmitted to a receiving device.
[0059] FIG. 6B is a flowchart of the steps in a process 665 for decoding and detecting errors in data received by a palmtop computer system (e.g., computer system 100 of FIG. 1) over a wireless link in accordance with one embodiment of the present invention. In one embodiment, process 665 is implemented by communication circuit 109 (specifically, DSP 120) of FIG. 5. In another embodiment, process 665 is implemented using processor 101 (FIG. 5) in lieu of DSP 120.
[0060] In step 670 of FIG. 6B, an analog signal is received by the receiver (e.g., signal transmitter/receiver device 108 of FIG. 5) and fed into an analog-to-digital converter (A/D). Digital samples are extracted and provided to step 675 of process 665 from the A/D converter.
[0061] In step 675 of FIG. 6B, the digital samples are provided to a detector for signal detection. In step 680, PN decoding of the digital samples is performed.
[0062] In step 685, in the present embodiment, the digital data are decoded using a FEC code such as a Hamming code. In accordance with the present invention, the FEC decoding is performed using reduced-size lookup tables which are memory efficient. Additional information regarding the use of reduced-size lookup tables in accordance with the present invention is provided in conjunction with FIGS. 7A, 7B and 9.
[0063] In step 690 of FIG. 6B, the CRC is implemented to verify the data were correctly received. In step 695, the data (when correct) are sent to the host (e.g., to computer system 100 memory).
Error Correcting Encoding and Decoding with Reduced-Size Lookup Tables
[0064] FIG. 7A is a flowchart of the steps in a process 700 for encoding a sequence of data bits in accordance with an embodiment of the present invention. Process 700 can be implemented by computer system 100 (FIG. 5) as computer-readable program instructions stored in a memory unit (e.g., ROM non-volatile 103 of FIG. 5) and executed by a processor (e.g., processor 101 or DSP 120 of FIG. 5). It is appreciated that process 700 may be applied in devices other than a palmtop computer where it is desirable to conserve memory space. Furthermore, it is appreciated that process 700 can be used in other applications where it is necessary or desirable to encode or decode a sequence of data bits.
[0065] In one embodiment, process 700 is implemented in the FEC encode step of process 600 (step 630 of FIG. 6A). In another embodiment, process 700 is implemented in the FEC decode step (step 685 of FIG. 6B).
[0066] In step 710 of FIG. 7A, the data to be encoded are separated into a multiplicity of smaller segments. For example, a sequence of K binary digits can be separated into two segments, although it is appreciated that more than two segments can be used in accordance with the present invention. In the present embodiment, the K binary digits are separated into segments of equal length (that is, each segment has the same number of digits), and the order of the K binary digits is maintained in the segments.
[0067] In step 720, a first lookup table (LUT) is used to encode the first segment. The first lookup table contains an encoded sequence for each of the possible combinations of digits in the first segment. The digits in the first segment are used as an index to locate in the first lookup table the encoded sequence corresponding to the particular combination of digits in the first segment.
[0068] In step 730, a similar approach as that just described is used to locate in a second lookup table the encoded sequence corresponding to the particular combination of digits in the second segment. If the sequence of K binary digits is separated into more than two segments, additional lookup tables are used to encode these additional segments.
[0069] In accordance with the present invention, the lookup tables used in steps 720 and 730 are of reduced size relative to a full-sized lookup table and therefore occupy less space in memory. A full-sized lookup table containing an entry for each possible combination K bits would have 2Kentries. For the case in which the K binary digits are separated into two equal segments of K/2 bits each, the first lookup table and the second lookup table would each have 2(K/2)entries. For example, for K=8, a full-sized lookup table would have 256 entries, while two reduced-size lookup tables would each have only 16 entries, or 32 entries in total (one-eighth the number of entries of the full-sized table). The reduced-size lookup tables therefore would occupy approximately one-eighth as much memory as a full-sized table. Thus, the reduced-size lookup tables are advantageously used in devices with limited memory space such as palmtop computers.
[0070] In accordance with the present embodiment of the present invention, the encoded sequences contained in the reduced-size lookup tables are generated in advance and stored. Additional information with regard to how the lookup tables are generated is provided in conjunction with FIG. 7B.
[0071] By generating the encoded sequences in advance, it is not necessary to perform the associated calculations in real time as the data are received by communication circuit 109. This provides a number of advantages, in particular for lower power devices such as palmtop computer systems. For example, looking up an encoded value in a table can be accomplished efficiently, using fewer processor cycles than a calculation of that encoded value. Because fewer processor cycles are used, power consumption is reduced and so a smaller battery can be used, keeping the device small in size and light in weight. In addition, the calculation can be performed outside of the lower power device using a more powerful host computer system and then downloaded into the device.
[0072] Continuing with reference to FIG. 7A, in step 740, the encoded sequences for each of the segments (from steps 720 and 730) are combined to form an encoded sequence for the entire sequence of K binary digits. In the present embodiment, the encoded sequences for the segments are combined using an XOR (exclusive or) operation (also referred to as a binary add or a modulo-2 operation). The encoded sequence for the K binary digits that is calculated in accordance with the present invention (using reduced-size lookup tables) is the same as the encoded sequence that would be generated using a full-sized lookup table.
[0073] FIG. 7B is a flowchart of the steps in a process 750 for encoding a sequence of bits in accordance with another embodiment of the present invention. Process 750 can be implemented by computer system 100 (FIG. 5) as computer-readable program instructions stored in a memory unit (e.g., ROM non-volatile 103 of FIG. 5) and executed by a processor (e.g., processor 101 or DSP 120 of FIG. 5). It is appreciated that process 750 may be applied in devices other than a palmtop computer where it is desirable to conserve memory space. Furthermore, it is appreciated that process 750 can be used in other applications where it is necessary or desirable to encode or decode a sequence of data bits.
[0074] In step 701 of FIG. 7B, the sequence of K binary digits that is to be encoded is separated into multiple segments. In the present embodiment, the segments are of equal length and the initial order of the digits is not changed. For example, for K=8, the sequence of binary digits can be represented as [X1X2X3X4X5X6X7X8]. For the case in which the sequence is separated into two segments of equal length, the first segment can be represented as [X1X2X3X4] and the second segment as [X5X6X7X8].
[0075] In the present embodiment, the sequence of binary digits is separated into two segments, although it is appreciated that more than two segments may be used in other embodiments. It will be obvious to one of ordinary skill in the art how the discussion below can be extrapolated to address those cases in which more than two segments are used.
[0076] In step 702 of FIG. 7B, binary zeroes are added to each segment so that the number of digits in each segment is equal to K. In the present embodiment, the binary zeroes are placed so that the binary digits in the initial sequence of K binary digits maintain their place. Thus, continuing the example above, the first segment is represented as [X1X2X3X40000] and the second segment as [0000X5X6X7X8].
[0077] In step 703 of FIG. 7B, each of the segments is encoded using a code generator G. A typical encoding scheme is usually generalized as mapping K-bit vectors X into N-bit vectors Y using a generator G specific to the code being used, in which:
[0078] [Y]=[X][G];
[0079] where Y=[Y1Y2Y3Y4Y5Y6Y7Y8Y9Y10Y11. . . YN]. Thus, if [Y]1represents the encoded version of the first segment and [Y]2represents the encoded version of the second segment, then:
[0080] [Y]1=[X1X2X3X40000][G]; and
[0081] [Y]2=[0000X5X6X7X8][G].
[0082] In step 704, the encoded version of the first segment [Y]1is stored in a first lookup table, and the encoded version of the second segment [Y]2is stored in a second lookup table.
[0083] In step 705, in the present embodiment, the encoded version of the first segment [Y]1and the encoded version of the second segment [Y]2are retrieved from their respective lookup tables and combined to generate an encoded sequence representing the entire sequence of K binary digits (from step 701). In the present embodiment, the encoded sequences for the first and second segments are combined using an XOR (exclusive or) operation (also referred to as a binary add or a modulo-2 operation).
[0084] Thus, for example, if K=8 and N=12, then:
[0085] [Y1Y2Y3Y4Y5Y6Y7Y8Y9Y10Y11Y12]=[X1X2X3X4X5X6X7X8][G].
[0086] However, as described above, in accordance with the present invention:
[0087] [X1X2X3X4X5X6X7X8]=[X1X2X3X40000]+[0000X5X6X7X8].
[0088] Accordingly:
[0089] [Y1Y2Y3Y4Y5Y6Y7Y8Y9Y10Y11Y12]=[X1X2X3X40000]+[0000X5X6X7X8][G].
[0090] In this example, [Y] would have 8 data bits (Xi) and 4 parity bits (Pi):
[0091] [Y]=[X1X2X3X4X5X6X7X8P1P2P3P4].
[0092] FIGS. 8A and 8B illustrate example cases in which a sequence of bits are encoded using reduced-size lookup tables in accordance with an embodiment of the present invention. In these examples, K is equal to 8 and N is equal to 12 (that is, the encoding scheme maps 8 bits into 12 bits).
[0093] With reference first to FIG. 8A, the 8-bit sequence 810 is separated into two 4-bit sequences 810aand 810b. The bits in sequence 810aare used as an index into lookup table 1 (815), which contains an encoded sequence corresponding to each possible combination of digits in sequence 810a. Similarly, the bits in sequence 810bare used as an index into lookup table 2 (816). The encoded versions of sequences 810aand 810bare retrieved from the lookup tables, and combined using binary adder 820 (e.g., an XOR gate) to generate encoded sequence 830. Sequence 830 has 8 data bits (Xi) and four (4) parity bits (Pi).
[0094] In accordance with the present invention, lookup tables 815 and 816 each contain only 2(K/2)by N entries (that is, 16×12 entries) instead of 2K×12 (256×12) entries. Thus, lookup tables 815 and 816, if combined, contain only 32×12 entries, or one-eighth the number of entries required by a full-sized lookup table. The memory space required to store lookup tables 815 and 816 is reduced by a commensurate amount relative to the amount of space needed to store a full-sized lookup table.
[0095] With reference next to FIG. 8B, the 8-bit sequence 840 is separated into four 2-bit sequences 840a, 840b, 840cand 840d. The bits in sequence 840aare used as an index into lookup table 1 (845), which contains an encoded sequence corresponding to each possible combination of digits in sequence 840a. Similarly, the bits in sequence 840bare used as an index into lookup table 2 (846), the bits in sequence 840care used as an index into lookup table 3 (847), and the bits in sequence 840dare used as an index into lookup table 4 (848). The encoded versions of sequences 840a, 840b, 840cand 840dare retrieved from the lookup tables, and combined using binary adder 820 (e.g., an XOR gate) to generate encoded sequence 830. Sequence 830 has 8 data bits (Xi) and 4 parity bits (Pi).
[0096] In accordance with the present invention, lookup tables 845, 846, 847 and 848 each contain only 2(K/4)by N entries (that is, 4×12 entries) instead of 2K×12 (256×12) entries. Thus, lookup tables 845, 846, 847 and 848, if combined, contain only 16×12 entries, or one-sixteenth the number of entries required by a full-sized lookup table. The memory space required to store lookup tables 845, 846, 847 and 848 is reduced by a commensurate amount relative to the amount of space needed to store a full-sized lookup table.
[0097] FIG. 9 illustrates an example case in which reduced-size lookup tables are used for decoding and error detection in a sequence of bits 910 in accordance with one embodiment of the present invention. In this example, K is equal to 8 and N is equal to 12. Thus, the sequence of bits 910 contains 8 data bits (Xi) and 4 parity bits (Pi).
[0098] The 8 data bits (Xi) are separated into two 4-bit sequences 910aand 910b. The bits in sequence 910aare used as an index into lookup table 1 (815), which contains an encoded sequence corresponding to each possible combination of digits in sequence 910a. Similarly, the bits in sequence 910bare used as an index into lookup table 2 (816). The encoded versions of sequences 910aand 910bare retrieved from the lookup tables, and combined using binary adder 820a(e.g., an XOR gate) to generate encoded sequence 930. Sequence 930 has 8 data bits (930a) and 4 parity bits (930b).
[0099] The 4 parity bits 910cfrom sequence 910 and the 4 parity bits 930bfrom sequence 930 are combined using binary adder 820b(e.g., an XOR gate) to generate syndrome 950. Syndrome 950 provides a known means for detecting whether there is an error in sequence 910.
[0100] In accordance with the present invention, as described previously in conjunction with FIG. 8A, lookup tables 815 and 816 of FIG. 9, if combined, contain only 32×12 entries, or one-eighth the number of entries required by a full-sized lookup table. The memory space required to store lookup tables 815 and 816 is reduced by a commensurate amount relative to the amount of space needed to store a full-sized lookup table. Thus, in accordance with this embodiment of the present invention, memory space is conserved for the decoding and error correction process (e.g., process 665 of FIG. 6B for received data) as well as for the encoding process (e.g., process 600 of FIG. 6A for data to be transmitted).
[0101] Tables 2A and 2B below illustrate example lookup tables containing encoded sequences for the case in which K=8 and N=12 in accordance with one embodiment of the present invention. Table 2A corresponds to the first lookup table (e.g., lookup table 815 of FIGS. 8A and 9) and Table 2B corresponds to the second lookup table (e.g., lookup table 816 of FIGS. 8A and 9). Thus, in accordance with the present invention, a first encoded sequence would be retrieved from Table 2A and a second encoded sequence would be retrieved from Table 2B, and these sequences would be combined to form an encoded sequence for K binary digits.
| TABLE 2A |
|---|
| Example First Lookup Table (K = 8, N = 12) |
| TABLE 2B |
|---|
| Example Second Lookup Table (K = 8, N = 12) |
SUMMARY
[0102] In summary, in accordance with the present invention, reduced-size lookup tables are used to encode and decode a sequence of K binary digits instead of a full-sized lookup table. A full-sized lookup table containing an entry for each possible combination of K bits would have 2Kentries, whereas for the case in which the K binary digits are separated into two equal segments of K/2 bits each, the reduced-size lookup tables would each have 2(K/2)entries and therefore occupy less space in memory. Further reductions in the size of the lookup tables are achieved by separating the sequence of K binary digits into smaller segments. The reduced-size lookup tables are advantageously used in devices with limited memory space such as palmtop computers.
[0103] In accordance with the present embodiment of the present invention, the encoded sequences contained in the reduced-size lookup tables are generated in advance and stored. By generating the encoded sequences in advance, it is not necessary to perform the associated calculations in real time, providing a number of advantages in addition to that described above. For example, looking up an encoded value in a table can be accomplished efficiently, using fewer processor cycles than an on-line calculation of that encoded value. As a result, power consumption is reduced and so a smaller battery can be used in a lower power device such as a palmtop computer, keeping the device small in size and light in weight.
[0104] Thus, the present invention provides a system and 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 addition, the present invention provides a system and method that do not consume a large amount of the available memory space in such devices.
[0105] The preferred embodiment of the present invention, a method and system providing a reduced table size forward error correcting encoder, is thus described. While the present invention has been described in particular embodiments, it should be appreciated that the present invention should not be construed as limited by such embodiments, but rather construed according to the below claims.
Claims
What is claimed is:
1. A method for encoding an initial sequence of binary digits, said initial sequence having a length of K bits, said method comprising the steps of:
a) separating, in a portable computer system disposed within a housing that is sized so that it is portable substantially within the hand of a user, said portable computer system comprising a handwriting recognition pad having a first region for alphabetic characters and a second region for numeric characters, said initial sequence of binary digits into a first segment and a second segment, said first segment comprising a first portion of said K bits and said second segment comprising a second portion of said K bits different from said first portion;
b) adding in said portable computer system one or more binary zeroes to said first segment and to said second segment such that said first segment and said second segment each have a length of K bits;
c) operating on in said portable computer system said first segment and said second segment with a code generator to generate a first encoded sequence and a second encoded sequence; and
d) forming in said portable computer system an encoded sequence for said sequence of binary digits by XORing said first encoded sequence and said second encoded sequence.
2. The method as recited in claim 1 wherein said step a) comprises the step of:
a1) separating said initial sequence of binary digits into segments of equal length.
3. The method as recited in claim 1 further comprising the step of, prior to said step a):
receiving said initial sequence of binary digits for decoding and error detection.
4. The method as recited in claim 1 further comprising the step of:
e) transmitting said encoded sequence for said initial sequence of binary digits.
5. The method as recited in claim 1 wherein said step c) further comprises the step of:
c1) storing said first encoded sequence in a first lookup table and said second encoded sequence in a second lookup table.
6. The method as recited in claim 5 wherein said step c) further comprises the steps of:
c2) generating an encoded sequence for each possible combination of binary digits in said first segment and in said second segment;
c3) storing in said first lookup table said encoded sequence for each possible combination of binary digits in said first segment; and
c4) storing in said second lookup table said encoded sequence for each possible combination of binary digits in said second segment.
7. The method as recited in claim 1 wherein said code generator is for an error correcting code.
8. The method as recited in claim 7 wherein said error correcting code is a Hamming code.