 |
Description  |
|
|
BACKGROUND OF THE INVENTION
The present invention relates to digital cellular communication systems and
more particularly to error correcting decoders employed in digital
cellular base stations and mobile phones.
In cellular communication systems, encoding/decoding procedures are applied
to transmitted voice and other data to reduce data errors. Prior to
transmission from a mobile phone or from a base station, encoding is
usually performed with either a block coding scheme or a trellis coding
scheme.
In the prior art, the most common cellular system procedure for encoding
messages at the sending end of the system is a two step procedure in which
a message is first encoded using a cyclic redundancy code (CRC) as an
outer code and then encoded using a trellis or block code as an inner
code. At the receiving end of the cellular system, the message is decoded
using the inner loop code to eliminate as many errors as possible through
forward error correction (FEC).
The message is then decoded using the outer CRC code to detect whether any
message errors still exist. The message is discarded if any error is
detected. In this prior art approach, a message is successfully decoded if
a maximum of
##EQU1##
errors exist in unknown word locations.
The most common block coding scheme is the Reed-Solomon scheme which is
best adapted for correcting burst data errors such as those that often
occur in cellular communication channels as a result of Rayleigh fading.
Trellis encoding is most commonly implemented by means of a convolutional
scheme, and is best adapted for correcting random data errors. Each of
these schemes has been variously embodied to limit data transmission
errors in cellular communication systems.
To provide for error correction and detection in the Reed-Solomon scheme,
data in a word to be transmitted is first encoded in an outer code
commonly by a CRC encoder which generates CRC error detection bits. Parity
bits are also generated to provide FEC in accordance with the Reed-Solomon
procedure. The CRC and FEC bits are combined with the data bits in the
word to be transmitted, such as from a mobile unit.
The received word is checked to determine whether the data bits received
are the same as the data bits transmitted. For this purpose, the received
word data is first passed through a Reed-Solomon decoder where FEC is
applied. The Reed-Solomon output is then passed through a CRC encoder.
The resulting CRC code bits and the received CRC code bits are compared. If
the compared CRC bits are the same, the data is accepted as valid. If a
difference is detected, the received data is discarded as erroneous.
Generally, a CRC encoder having a longer CRC code provides better error
protection by making it less likely that a data error will go undetected.
Prior art decoders, employing Reed-Solomon or other block or trellis codes,
have been limited in error protection performance as a result of limited
error correcting capability. In addition, the amount of computer capacity
required for implementation of the Reed-Solomon or other coding procedures
respectively in prior art decoders has limited cost effectiveness and the
cost/benefit ratio in providing error protection in cellular communication
products.
SUMMARY OF THE INVENTION
The present invention is directed to a digital cellular communication
system and method in which error correction decoding is performed with
better error correcting capability and with greater product cost
effectiveness.
A cellular receiver in a cellular communication system comprises means for
receiving and demodulating a transmitted signal representing a code word
containing a message encoded with an error detecting code as an outer code
and enclosed with an error correcting code as an inner code. Means are
provided for decoding the demodulated signal including means for
generating a list of estimates of the code word from the demodulated
signal and means for operating an error correcting decoder with the error
correcting code to decode estimates of the code word. The decoding means
further includes means for operating an error detector decoder with the
error detecting code to process decoded code word estimates and determine
whether an error exists in each decoded code word estimate that is
processed, means for generating as an output signal any decoded code word
estimate detected to be error-free, and means for generating a code word
error if no decoded code word estimate is detected to be error-free.
BRIEF DESCRIPTION OF THE DRAWINGS
The accompanying drawings, which are incorporated in and constitute a part
of this specification, illustrate a preferred embodiment of the invention
and together with the description provide an explanation of the objects,
advantages and principles of the invention. In the drawings:
FIG. 1 shows a block diagram for a digital cellular communication system in
which the present invention is embodied in its preferred form;
FIG. 2 shows a subsystem block diagram for base station circuitry employed
in the system of FIG. 1;
FIG. 3A provides an overview functional flow diagram for a cellular
communication system operated in accordance with the present invention;
FIG. 3B illustrates a Reed-Solomon decoder employed in the base station
circuitry of FIG. 2 in accordance with the present invention;
FIG. 4 shows a general flow chart for a decoding procedure employed in the
decoder of FIG. 3 in accordance with the present invention;
FIG. 5A shows with greater detail Reed-Solomon decoding as employed in FIG.
4 in accordance with the present invention;
FIG. 5B provides greater detail for a symbol erasure selector employed in
the flow chart of FIG. 4;
FIGS. 6A and 6B provide more detailed flow charting for CRC checking
employed in the procedure of FIG. 4;
FIG. 7 illustrates a routine employed in the procedure of FIG. 4 to
determine Reed-Solomon symbol reliability values from soft decision data
bits generated by a demodulator module in the base station circuitry of
FIG. 2;
FIG. 8 graphically represents a transmitted data word;
FIG. 9 details a Reed-Solomon coding scheme used for the data word of FIG.
8 with n word symbols, p parity symbols, and k message symbols;
FIG. 10 illustrates a typical assignment of bit erasures by the selector of
FIG. 5B to an n symbol word;
FIG. 11 shows a typical prior art bit structure for a transmitted word in a
typical prior art cellular system employing Reed-Solomon decoding; and
FIG. 12 comparatively shows a bit structure for a transmitted word in a
cellular system having a base station that provides decoding in the
preferred embodiment in accordance with the present invention.
DESCRIPTION OF THE INVENTION
A digital cellular communication system 10 is shown in FIG. 1 in which a
preferred form of the present invention is embodied. The system 10 is
operative in a defined geographic region such as all or part of a
metropolitan area.
The cellular system 10 includes numerous mobile phone units, as represented
by four illustrated units 12A through 12D. Communication links may be
established between the mobile units 12A-12D and a base station for the
communication cell within which the mobile unit(s) may be located. In this
illustrative case two base stations 14A and 14B are shown.
Respective pairs of diversity antennae A1, B1 and A2, B2 are provided at
the base stations to provide for receiving diversity signals from a
transmitting mobile unit. In the preferred embodiment, the diversity
signals are processed to remove errors and develop high quality
demodulated voice signals in accordance with the invention.
A base station controller 16 provides system management functions through
regulation of the operation of the base stations 14A and 14B and by
establishing communication links with a public telephone system 18.
As shown in FIG. 2, circuitry for the base station 14A or 14B includes an
RF receiver having a low noise amplifier 20 that receives signals from
diversity antennae A and B. Next, a down-conversion module 22 provides
signal downconversion from RF to the baseband and then provides analog-to
digital conversion through a signal sampling procedure.
The output digital signal from the downconversion module 22 is applied to a
demodulator means or a demodulator module 24 where the originally
modulated signal is demodulated. The originally transmitted signal is
modulated using .pi./4, shifted differential encoded quadrature phase
shift keying.
The demodulator means 24 is structured in accordance with the present
invention to provide improved base station demodulation in the sense that
superior, relatively complex demodulation algorithms are enabled to be
implemented cost effectively in real time with state-of-the-art processor
hardware. As a result, cellular base station products can be manufactured
and supplied to the market at competitive prices and simultaneously
provide superior demodulation performance, higher quality voice channels,
and extended system communication coverage and user capacity.
The base-station demodulator means 24 can be employed in various kinds of
digital cellular communication systems, such as the conventional time
division multiple access system. Further, the present invention can also
be applied to mobile phone unit receivers to provide improved demodulation
in the phone units in a manner similar to that described herein for base
stations.
The output of the demodulator 24 is coupled to a decoder/controller module
26 where bit errors are detected and forward error correction is applied
to the demodulated signal. A decoded and corrected signal is generated and
sent for voice processing in the base station controller 16. The
decoder/controller module 26 also provides high level control and system
management for the base station circuitry.
As previously indicated, the voice signal (having originated from a
particular, connected mobile unit) is linked to the public telephone
system 18 for connection to any other phone or mobile unit. Return voice
signals from the connected phone are processed by base station
transmission circuitry (not shown) for transmission to the originally
connected mobile unit.
Transmitted signals are encoded to increase message reliability preferably
with the use of an outer code for error detection and an inner code for
error correction. The inner code is preferably an error correcting block
code and the outer code is preferably an error detecting cyclic redundancy
code (CRC). The preferred block code is the Reed-Solomon (R-S) code. After
demodulation, received signals are sent for R-S decoding with error
detection provided by the CRC.
INVENTION OVERVIEW-MESSAGE TRANSMISSION AND DECODING PROCESS IN DIGITAL
CELLULAR COMMUNICATION SYSTEM
The present invention has application to cellular systems when both an
outer error detection scheme and an inner error correction scheme are
employed to provide code protection for transmitted messages. Further, the
inner error correction scheme needs to have the capability of developing a
collection of transmitted code word estimates, preferably ranked from best
estimate to worst estimate.
Generally, an inner error correction decoder produces a list of estimates
of the transmitted code word. This list may be ordered from the most
likely candidate to the least likely candidate. For Reed-Solomon decoders,
this list is generated by moving some number of erasure locations
preferably from the most likely symbol error positions to less likely
error positions. For Trellis codes, the ordered list is similarly
developed by generating code words for the most likely path to less likely
paths.
Once the ranked word estimate list is generated, the outer error detection
decoder is applied to the list of transmitted code word estimates,
beginning with the most likely word estimate. If the outer error detector
finds a code word estimate without an error, that code word estimate is
declared to be correct. If all code word estimates are found to be in
error, a word error is declared.
As shown in FIG. 3A, an overall message transmitting and decoding procedure
30 starts with a data input 29 in the form of a digital data word.
Generally, sequentially input data words represent an analog waveform
corresponding to voice or other sound to be transmitted by the mobile
unit.
Outer CRC coding is first applied to the data word as indicated by a block
31. A resulting encoded message 32 is applied as an input to a block 33
that employs an inner trellis encoding scheme or, as preferred in the
present embodiment, a block encoding scheme.
An output channel code word 34 is generated by the encode block 33. With
the preferred R-S block coding, data and parity bits are separately
grouped in the channel code word 34. With trellis coding, the channel code
word structure is not systematic, i.e. data bits are encoded into a code
word in which the bits have no direct correspondence to the original data
bits.
The channel code word is then transmitted over the transmission channel as
indicated by a block 35. The received channel code word, indicated by a
block 36, may be the same as the transmitted word or, if channel error has
been introduced, it will differ from the transmitted word in accordance
with the error.
Next, trellis or block decoding, preferably R-S block decoding, is
performed as indicated by a block 37 to generate decoded message estimates
C.sub.1 through C.sub.e as indicated by a block listing 38. Finally, a CRC
check is made as indicated by a block 39 on successive message estimates,
and an accepted word estimate is generated as indicated by a block 40 when
one of the word estimates checks error-free. If no word estimate checks
error-free, the message is discarded as indicated by a block 42.
DECODER
The decoding means 26, includes a digital signal processor (DSP) 41 for R-S
symbol assembly and decoding as shown in FIG. 3B. A soft bit output 43 is
applied from the demodulator module 24 to the input of the decoder
processor 41, and it is also applied to a bit generator 45 that generates
a hard bit for each soft bit. The hard bit output is also applied to the
input of the processor 41.
The hard bit output 45 defines each message bit as a 1 or a 0 with some
probability of error. The soft bit output 43 defines each message bit with
a value in a predetermined scale of values between -1 and +1 thereby
indicating the relative reliability of the valuation of each message bit.
If the soft bit value is positive, it is interpreted to be a hard 1 bit.
If the soft bit value is negative, it is interpreted to be a hard 0 bit.
The decoding means 26 operates under program control and in accordance with
the invention to decode each R-S encoded message word with improved
performance, i.e., higher message reliability with better product cost
effectiveness.
ENCODED WORD STRUCTURE
As previously indicated, inner and outer coding is used in cellular systems
when transmitting data across a data channel so that the reliability of
received data can be improved through error correcting and detecting
processes. The R-S block coding is preferred for use in this embodiment
because it is very effective where burst errors are commonly encountered,
as is the case in cellular systems.
Generally, as practiced in the prior art, R-S coded messages can be decoded
accurately, i.e., can have errors corrected, when a number e of symbol
errors in unknown bit positions does not exceed a specific determinable
value. In addition, R-S coded messages can be decoded correctly in the
prior art when 2e symbol errors exist in known bit locations. As will
become more evident hereinafter, the present invention provides an
improvement over the prior art through extended error correcting
capability in the decoding process.
In FIG. 8, there is shown a graphical representation 50 of the transmitted
word structure for an R-S encoded message. A message portion 52 of the
word 50 includes a data section 54 in which a predetermined number of
symbols carry digital message data.
If the received symbols are the same as the transmitted symbols in the data
section 54, the transmission has been executed with complete accuracy. An
outer parity check code, preferably in the form of a cyclic redundancy
check (CRC) code, is employed in a CRC code section 56 of the word message
portion 52 to code the message data. The CRC code operates as an error
detector and generates a flag if an error is detected in a transmitted
message.
If an error is detected, retransmission may occur until no CRC error flag
occurs and the message is accepted. As more fully described subsequently
herein, an inner R-S forward error correction (FEC) code in an FEC word
portion 58 encodes the message formed by the message data and the CRC. The
FEC code operates with the error detection code (CRC) in accordance with
the invention to reduce significantly the retransmission rate in cellular
systems and thereby improve cellular communication reliability.
The structure of the inner R-S coding is illustrated in FIG. 9. In the
general case, a transmitted word 50 consists of n symbols S. The message
portion 52 of the word 50 has k symbols S and the FEC word portion 58 has
n-k or p symbols S for implementation of the R-S coding. An R-S decoder is
known to be capable of correcting up to
##EQU2##
errors or [n-k] erasures.
DECODING PROCEDURE FOR THE INVENTION
A decoding procedure 70 shown in FIG. 4 is executed in the DSP 41 and
operates with the preferred R-S coding scheme and is structured in
accordance with the invention to provide improved cellular receiver or
base station operation and other improvements in cellular communication
systems. The procedure 70 is executed for each transmitted code word
received by the receiver, i.e. the base station receiver in the preferred
embodiment.
Generally, in accordance with the invention, a list of estimates is made
for the transmitted code word, and a search is made during inner code
processing through all or some of the transmitted word estimates, i.e.
words with different symbol erasure combinations. The outer CRC decoding
procedure is used to detect properly decoded messages. In effect, the
random error correction capability for transmitted code words can be
doubled with use of the invention. Furthermore, when reliability
information is available for the received symbols, a limited search can be
employed to reduce the computational load on the decoder and thereby
reduce the risk that the CRC will fail to detect an erroneously decoded
message.
Startup for the procedure 70 occurs in a block 72 and a program loop 73
makes a symbol error search for the current word. In one of the preferred
embodiments of the invention, an entry selector block 74 selects all
possible combinations of message data symbol erasures in the word for
error testing in successive iterations of the program loop 73. Thus, a
full search is made for all possible combinations of p erasure positions
out of n symbols.
The full search cna involve up to
##EQU3##
combinations. Since the CRC detects all Reed-Solomon decoded message
errors, all received words with p or fewer randomly occurring symbol
errors will be correctly decoded.
For example, an R-S code may have a total number n of symbols equal to 10
of which 8 may be the number k information symbols. Therefore, in this
example, there are a number p of parity symbols equal to 2. Decoding with
a (10,8) R-S code can thus be performed successfully for 2 or fewer
erasures. Under prior art procedures, only p/2 or 1 random error may be
corrected with R-S decoding. With the use of searching in accordance with
the present invention, a search is made of all or some of the possible
erasure combinations which number
##EQU4##
or 45. As a result, the present invention enables correction of 2 random
errors in the example of a (10,8) R-S code.
In the limited search, a subset of the R-S symbols are searched where the
number n' of symbols searches is less than the total number n of symbols.
The subset symbols are preferably selected on the basis of reliability
information as more fully described subsequently herein.
As an example of a limited search executed in accordance with the
invention, a (15,11) R-S code corrects up to four erased symbols. A
complete search in accordance with the invention requires decoding of
##EQU5##
or 1365 erasure quadruplet combinations. If this is narrowed to the 8
least reliable symbols, a limited search in accordance with the invention
requires decoding of
##EQU6##
or 70 erasure quadruplet combinations. Thus, significant computer load
reduction may be achieved with the use of a limited search where a slight
reduction in decoder performance is acceptable.
For each selection of data symbol erasures, the digital data for the
selected symbols is switched to the opposite binary value and a block 76
decodes the modified word in accordance with an R-S decoding procedure.
Another test block 78 checks the decoded message by means of a CRC check,
and the decoded word is declared error-free for further processing in a
block 80 if the CRC check detects no error.
In that event, the message data in the modified word having CRC
verification is determined to be true to the transmitted message data and
the modified word is accepted as a corrected word. A forward error
correction has thus been made.
However, if the CRC check finds an error in the message data in the
modified word, an indication is made that the erased symbols did not
include all of the error symbols and thus did not correct the message data
error(s). The program loop 73 then returns to the test block 74 for
another iteration with the next possible symbol erasure combination.
Loop iterations are repeated until the test block 78 provides an error-free
check or until the test block 74 has processed all possible symbol erasure
combinations.
When a search has been exhausted without discovery of symbol errors, a
block 82 declares the word to have an uncorrectable error, and the
uncorrected word is processed for retransmission or abandonment in
accordance with system procedural requirements. A failure may occur, for
example, if the number of symbol errors exceeds p.
REED-SOLOMON ENCODING AND DECODING--BACKGROUND INFORMATION
Generally, R-S codes are a class of linear block codes with the following
properties:
1) non-binary (q element alphabet)
2) cyclic
3) can correct y errors in unknown positions and z errors in known
positions as long as:
2y.sub.n +z.>n-k
where: n is the number of symbols in the code word, k is the number of data
symbols in the code word, and n-k=p is the number of parity symbols in the
code word.
Code words for linear block codes are generated by augmenting k data
symbols with p parity symbols. The resulting code word has n symbols.
Reed-Solomon codes are non-binary. Each symbol within a code word can take
on any one of q values. R-S codes are cyclic codes. That is, if:
(S.sub.0, S.sub.1, S.sub.2, . . . , S.sub.n-1)
is a legitimate code word, then so are:
(S.sub.1, S.sub.2, S.sub.3, . . . , S.sub.n-1, S.sub.0), (S.sub.2, S.sub.3,
S.sub.4, . . . , S.sub.0, S.sub.1),
etc.
Cyclic codes with symbols that come from a q element alphabet are based on
Galois fields. The multiplication and addition operations for the elements
or symbols are defined by the Galois field and in turn the Galois fields
are defined by an irreducible polynomial G(x).
The first step in defining an R-S code is to define what is meant by
addition and multiplication of elements (symbols). An R-S code is then
fully defined by the selection of a generator polynomial. Although many
more generator polynomials can be found, one can be selected for a
particular n-k as follows:
##EQU7##
A number of decoding schemes have been developed that exploit the field
characteristics of R-S codes. Both time domain and transform domain
algorithms have been used. Typical prior art algorithms find the closest
code word to the received code word (the code word that differs from the
received word by the fewest number of symbols) without exhaustively
searching all code word possibilities. The total number of code words is
q.sup.k
Erasures can also be introduced in prior art R-S decoding algorithms. Such
algorithms then find the code word that differs from the received word by
the least number of symbols, excluding the erasure locations.
In typical prior art calculating procedures for R-S decoding, the bit
position from right to left is defined by x to the power that corresponds
in number to the bit position. A locator polynomial is solved for roots to
get bit positions, and an evaluator polynomial uses the roots to get the
magnitude at the root locations.
Message encoding employs two steps. The data is first encoded using a CRC,
then the message (CRC parity bits and data) is coded using a Reed-Solomon
code. To decode the received word, Reed-Solomon decoding is used to
eliminate as many errors as possible. If message errors still exist, they
are detected by the CRC and the received message is discarded. This prior
art approach normally successfully decodes received messages with
##EQU8##
errors in unknown locations.
INVENTION DECODING PROCEDURES--GREATER DETAIL
With reference to the R-S decoding block 76 in FIG. 4 and FIG. 5A, it is
well known that a Reed-Solomon coded message can be accurately decoded
when 2T+E.ltoreq.d-1 where:
d is the minimum distance between code words,
T is the number of errors in unknown symbol locations (symbol errors),
E is the number of symbol locations known to be unreliable (symbol
erasures).
The maximum number of errors in unknown locations that can be corrected is
##EQU9##
In accordance with the present invention, all or some of the erasure
assignment combinations of d-1 symbol positions are searched. Therefore,
if the CRC successfully determines whether a decoded word is correct, n
(d-1) randomly occurring errors can be corrected with use of the
invention.
The R-S decoder 76 is shown in greater detail in FIG. 5A.
A typical assignment of p erasures to an n symbol word is shown in FIG. 10.
In the process of choosing erasures for a limited search, n-k erasures are
picked out of n symbol locations by making use of symbol reliability
information. Let:
(SR.sub.1, SR.sub.2, . . . SR.sub.n)
represent the reliability of each symbol. Symbol reliability is determined
from the reliability of input signal bits, i.e. from the soft bit values
for hard bits in each symbol. For a full search, no reliability
information need be used in selecting erasure locations since all possible
assignments of n-k erasures to n positions are tried.
The number of combinations is given by
##EQU10##
In a partial search, the n' least reliable positions are chosen out of n
positions for the search. The number of combinations in a partial search
is given by:
##EQU11##
Symbol reliability information may be used to select some subset of
received symbols for the erasure search. Thus, the n' (n'<n) least
reliable symbols are selected as possible erasures. The
##EQU12##
combinations of erasures is then searched to find a decoded message that
passes the CRC test. With use of the reliability based search, fewer
computations are required and fewer chances occur for the CRC to be
penetrated. If the symbol reliability information is good, most (but
necessarily not all) received words with p or fewer errors are corrected.
More particularly, as shown for the preferred embodiment in FIG. 5B, a
partial-search codebook for each successive message word is created in
accordance with a logic flow diagram routine 81. In a block 82, symbols in
the word are ranked preferably from least reliable to most reliable.
Next, a predetermined number x of least reliable symbols are selected for
error searching in a block 84. A listing is then made in a block 86 of all
combinations of a preselected number of erasure locations y for the x
least reliable symbols, and the listing is stored as the codebook for the
current message word as indicated by block 88.
Generally, in accordance with CRC encoding, D data bits can be protected
with P parity bits as follows:
##EQU13##
In decoding, a CRC check is generally made as follows: b(x), indicated by
block 90 in FIG. 6B, represents the received message.
d(x), representing the data portion of the message and R(x) representing
the parity portion of the message are separated as indicated by block 92.
That is:
##EQU14##
Next, block 94 generates
##EQU15##
Then, as indicated by blocks 96 and 98 if:
R.sup.1 (x)=R(x), i.e. R.sub.P-1 =R.sup.(1).sub.P-1 and R.sub.P-1
=R.sup.(1).sub.P-1. . . ,
then the received message passes the CRC check. Otherwise, it fails as
indicated by blocks 96 and 100.
Accordingly, in the procedure 70 of FIG. 4, the CRC check block 78 operates
as more fully shown in FIG. 6A. After startup, a counter e for code words
with different erasures is set equal to 1 in a block 100. Next, the CRC
outer error detector is applied to C.sub.e in a block 102, and a test
block 104 checks the results to determine whether an error has been
detected.
If there is no error, a block 106 sets C equal to C.sub.e as the corrected
message word for further processing. Otherwise, a test block 108 returns
the program flow to a block 110 that advances the e counter for a repeat
execution of the block 102 for the next code word in the codebook 75 (FIG.
5A). If the code word C.sub.e is reached in the search without finding an
error-free code word, the block 108 flags an error as indicated by a block
110. The current message word is then trashed, and a retransmission of
that word may be initiated.
In generating R-S symbols from soft decision information and in defining
R-S symbol reliability, the demodulator 26 generates a stream of
soft-decision values with each value corresponding to a bit that has been
transmitted across the channel. For an m bit per symbol R-S code, an R-S
symbol number and an R-S symbol reliability number are assigned to each m
soft-decision block.
To generate an R-S symbol from m soft-decision values, the format shown in
FIG. 7 is assumed for soft-decision values. If a soft-decision value is
positive, a hard-decision value of 1 is chosen. If the soft decision value
is negative, a hard-decision value of 0 is chosen. To generate an R-S
symbol, (RS.sub.1, RS.sub.2, RS.sub.3. . . RS.sub.m), from m soft-decision
values, (SD.sub.1, SD.sub.2, SD.sub.3. . . SD.sub.m), the following rule
is used:
The reliability (SR) of the resulting symbol is given by
##EQU16##
An R-S symbol is more reliable with larger values of the reliability SR.
COMPARATIVE PERFORMANCE OF INVENTION OVER PRIOR ART
The present invention addresses the need to transmit control signals
reliably across a radio interface. It is particularly applicable in the
| | |
