Architecture for a faster max* computation

Details Architecture for a faster max* computation Architecture for a faster max* computation

2003-07-28

2004-09-28

Williams, Howard (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

Coding by table look-up techniques

C341S094000, C375S265000, C375S341000, C714S796000

Reexamination Certificate

active

06798366

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to wireless communications systems and, more particularly, to turbo decoders used in wireless communications.
2. Description of the Related Art
This section is intended to introduce the reader to various aspects of art that may be related to various aspects of the present invention, which are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present invention. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art.
Although the first mobile telephone system for public use was developed in 1946, and improved in 1965, modern wireless technology was introduced in 1970 as the Advanced Mobile Phone Service (AMPS), which is the American analog cellular standar. Despite this early development, the first commercial cellular system began operating in Chicago in 1983, thus giving rise to one of the fastest growing consumer technologies in history. Indeed, so many people subscribed to cellular service by the mid-1990s that the critical problem for cellular carriers became that of capacity. Accordingly, cellular providers had to develop ways to derive more capacity.
The most extreme and costly method to increase capacity involved reducing cell sizes and introducing additional base stations. However, in many large metropolitan areas, it became increasingly difficult and costly to obtain permits to erect base stations and antennas. Accordingly, cellular providers desired a solution for increasing system capacity without requiring more base stations. One proposed solution involved the use of digital technology.
The first all digital systems, Personal Communication Services (PCS), were introduced in the United States in the mid-1990s. PCS is referred to as the second generation wireless service, with the first generation mobile telephone service being the analog service mentioned above. Various digital wireless technologies were developed, including Time Division Multiple Access (TDMA), Code Division Multiple Access (CDMA), and Global System for Mobile Communications (GSM). Because the advent of digital wireless communications greatly increased the capacity of wireless networks, cellular providers had more capacity to sell to eager subscribers. Thus, the rate of cellular subscriptions continued to increase.
There is currently a move to develop a global standard for wireless technology, which has been dubbed the third generation or “3G” wireless standard. It is likely that the third generation wireless technology will be an enhanced version of one of the three digital wireless technologies mentioned above. It is expected that such standardization will not only lead to further increases in capacity, but also lead to lower cost and increased efficiencies due to standardized networks that may be shared amongst various cellular providers.
As a result of the third generation developments, and in view of the likely continued increase in consumer demand, portable wireless applications, such as voice and/or data communications, will require greater rates at lower channel signal-to-noise ratios than ever before. Accordingly, developers are seeking techniques that provide faster and more reliable digital communications, while also reducing power consumption of the battery-powered portable devices used for such communication.
To achieve more reliable data transmission, more advanced error correcting techniques are being considered. One error correction technique known as turbo coding has a greater error correction capability than previously used codes, and it is specified as one of the coding options for the third generation standard. Indeed, the introduction of turbo codes in 1993 was considered as one of the most exciting and important developments in digital communications in many years. By using turbo codes, error correction can be done within 0.7 db of the Shannon limit, which is the theoretical limit of decoder performance. However, turbo coding and decoding is not a trivial exercise, and coders/decoders (codecs) based on turbo codes are quite complex. Such complexity, in the digital world, typically leads to slower processing and greater power consumption than other coding techniques that may be under consideration.
Turbo decoders, in particular, utilize complex decoding algorithms. Specifically, turbo decoders operate in an iterative fashion and, thus, require a number of computations to decode the signal accurately. The iterative decoding algorithm is typically performed in log space and referred to as the log-MAP decoding algorithm. One of the reasons that the log-MAP algorithm is useful involves the computational phenomenon that while multiplications and divisions are difficult in linear space, such multiplications and divisions become additions and subtractions, respectively, in log space. Although additions and subtractions in linear space become more difficult in log space, there are typically many more multiplications and divisions in linear space MAP decoding, so it generally makes sense to convert computations to log space and use the log-MAP algorithm. Indeed, if the MAP algorithm was performed in linear space, it would be so complex that it would be difficult, if not impossible, to achieve real time operation. Other advantages of operating the log-MAP algorithm are well known and need not be repeated herein.
One awkward computation when operating the log-MAP algorithm is the log of the sums of exponentials: ln(e
a
+e
b
+e
c
+ . . . ). This problem can be simplified using the following formula: ln(e
a
+e
b
)=max (a,b)+ln(1+e
−|a−b|
). This entire operation is often referred to as the max* function. Because of the computational complexity of the max* operation, a further simplification is often made by simply ignoring the second term of the max* function. This algorithm is typically referred to as the max-log-MAP algorithm. Although the max-log-MAP algorithm reduces the number of operations required, it also increases the bit error rate of the decoder because the computations are not as accurate. Indeed, it has been shown that coding gain of a log-MAP decoding is superior by 0.7 db as compared to the max-log-MAP algorithm.
Even in codecs that utilize the max* operation, different methods exist for implementing this function. For example, digital signal processors (DSPs) are often used to perform the various codec functions, including the max* operation. However, DSPs are typically general purpose processors that must be programmed appropriately to perform the desired functions. As such, DSP codecs are typically slower and more power hungry than custom hardware codecs.
In custom hardware codecs, the time required to perform a max* operation is linearly proportional to the clock speed of the codec, and the power consumption is proportional to the number of gates used in the circuitry to perform the max* operation. To date, improvements in speed have largely been accomplished through increases in clock speed and optimization of gate design, but these techniques produce only limited improvements. Accordingly, it would be advantageous to identify other techniques to increase speed and/or reduce power consumption.
SUMMARY OF THE INVENTION
Certain aspects commensurate in scope with the originally claimed invention are set forth below. It should be understood that these aspects are presented merely to provide the reader with a brief summary of certain forms the invention might take and that these aspects are not intended to limit the scope of the invention. Indeed, the invention may encompass a variety of aspects that may not be set forth below.
In accordance with one aspect of the present invention, there is provided a turbo decoder having at least one lookup table adapted to process selected lower significant bits of a digital sig

Affiliated with

Also associated with

Rating

Architecture for a faster max* computation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Architecture for a faster max* computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Architecture for a faster max* computation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3257748