+

WO2006013361A1 - Methode et appareil pour accroitre l'efficacite de calcul dans une estimation sequentielle - Google Patents

Methode et appareil pour accroitre l'efficacite de calcul dans une estimation sequentielle Download PDF

Info

Publication number
WO2006013361A1
WO2006013361A1 PCT/GB2005/003042 GB2005003042W WO2006013361A1 WO 2006013361 A1 WO2006013361 A1 WO 2006013361A1 GB 2005003042 W GB2005003042 W GB 2005003042W WO 2006013361 A1 WO2006013361 A1 WO 2006013361A1
Authority
WO
WIPO (PCT)
Prior art keywords
symbols
receiver
channel
sequence
state
Prior art date
Application number
PCT/GB2005/003042
Other languages
English (en)
Inventor
Simon Richardson
Original Assignee
Ttpcom Limited
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Ttpcom Limited filed Critical Ttpcom Limited
Publication of WO2006013361A1 publication Critical patent/WO2006013361A1/fr

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L25/00—Baseband systems
    • H04L25/02—Details ; arrangements for supplying electrical power along data transmission lines
    • H04L25/03—Shaping networks in transmitter or receiver, e.g. adaptive shaping networks
    • H04L25/03006—Arrangements for removing intersymbol interference
    • H04L25/03178—Arrangements involving sequence estimation techniques
    • H04L25/03184—Details concerning the metric
    • H04L25/03197—Details concerning the metric methods of calculation involving metrics
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L25/00—Baseband systems
    • H04L25/02—Details ; arrangements for supplying electrical power along data transmission lines
    • H04L25/03—Shaping networks in transmitter or receiver, e.g. adaptive shaping networks
    • H04L25/03006—Arrangements for removing intersymbol interference
    • H04L2025/0335—Arrangements for removing intersymbol interference characterised by the type of transmission
    • H04L2025/03375—Passband transmission
    • H04L2025/03401—PSK
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L25/00—Baseband systems
    • H04L25/02—Details ; arrangements for supplying electrical power along data transmission lines
    • H04L25/03—Shaping networks in transmitter or receiver, e.g. adaptive shaping networks
    • H04L25/03006—Arrangements for removing intersymbol interference
    • H04L25/03178—Arrangements involving sequence estimation techniques
    • H04L25/03203—Trellis search techniques
    • H04L25/03229—Trellis search techniques with state-reduction using grouping of states

Definitions

  • the present invention relates to a method of and apparatus for reducing the computational load in estimating the most likely received sequence of symbols in a telecommunications system where coding during transmission places constraints of the sequence of symbols that is transmitted.
  • signals propagating between a transmitter and receiver are subject to interference, noise, and multipath distortion.
  • Multipath distortion arises because the signal may undergo multiple reflections. This can result in the received signal being the sum of the transmitted signal and a time delayed (i.e. earlier transmitted) version of the signal
  • Received Signal ⁇ t transmitted signal(t - direct path) + a transmitted signal(t - multipathl) + ⁇ transmitted signal(t - multipath2 )+ ...
  • the symbol received by a receiver is the result of convolving the transmitted signal with the impulse response of the transmission channel.
  • the received signal can be represented by
  • FIG. 1 schematically illustrates a transmission path from a transmitter 1 to a receiver 2.
  • a direct path 4 exists but a further path 6, introducing multipath distortion, also exists.
  • the reflector 8 that gives rise to the multipath distortion may have a surface with a complex dielectric coefficient such that the multipath signal has a phase change and amplitude change with respect to the direct signal as well as a time delay.
  • Figure 2 shows a constellation diagram for a transmission scheme having eight individual symbols equally spaced around a unit circle.
  • the effect of multipath distortion can be seen if, for simplicity, we suppose that the multipath delay introduces a delay equivalent to twice the inter symbol period of the transmission scheme and the reflector introduces a 90° phase shift and reflects 50% of the signal towards the receiver.
  • the sequence received from the reflector is equivalent to multiplying each of these sequence streams by 0.5j where j is the imaginary operator, and delaying it by two symbols
  • the original burst of symbols labeled Tl, T2 and T3 in Figure 3 gives rise to five received symbols Rl to R5 when received at the receiver.
  • the delayed version of the first transmitted symbol interferes with the reception of the third symbol causing the received symbol R3 to be displaced from its true position in the constellation diagram as marked T3.
  • any subsequent transmitted symbols can be interfered with by received symbols from the multipath direction, R4 and R5.
  • a method of estimating a sequence of symbols, where the symbols are subject to multipath distortion in a transmission channel comprising pre-calculating a plurality of products of a transmitted symbol and channel coefficients.
  • the multipath distortion is compensated for using an equalisation technique.
  • an apparatus for estimating a sequence of symbols where the symbols are subject to multipath distortion in a transmission channel, wherein the apparatus is arranged to pre-calculate a plurality of products of a transmitted symbol and channel coefficients.
  • the apparatus is an EDGE enabled receiver.
  • a computer program for causing a programmable data processor to perform the method as claimed in claim 1.
  • Figure 1 schematically illustrates a situation in which multipath distortion can occur
  • Figure 2 illustrates a constellation diagram used in a telecommunication transmission scheme
  • Figure 3 schematically illustrates the effect of multipath distortion on signals received at a receiver, the signals being represented on a constellation diagram
  • Figure 4 is a circuit diagram of a convolutional encoder
  • Figure 5 is a diagram of the state transitions and output symbols for the convolutional encoder shown in Figure 4;
  • Figure 6 shows a first step in a trellis decoding scheme
  • Figure 7 shows a second step in a trellis decoding scheme
  • Figure 8 shows a third step in a trellis decoding scheme
  • Figure 9 is a schematic diagram of a receiver constituting an embodiment of the present invention.
  • the Viterbi algorithm is well known for its use in decoding data streams which have been subjected to forward error correction in order to enhance communication performance in the presence of the noise and distortion, such as multipath distortion, arising from the communications channel.
  • Forward error correction can be performed using convolutional encoding.
  • Convolutional encoding can be performed verily easily in hardware. It is generally performed using a series of shift registers in conjunction with the modulo 2 adders.
  • the modulo 2 adders can be implemented as a cascade of exclusive - OR gates. Viterbi decoding is a complex process, so it is useful to consider a simple example.
  • a simple convolutional encoder is in Figure 4.
  • the encoder comprises two delay elements 10 and 12 connected in series. Each delay element introduces a delay of 1 clock cycle T which is also commonly denoted as Z "1 .
  • the undelayed input, the input delayed by Z "1 and a copy of the input delayed by Z "2 (2 delays) is summed by a first modulo 2 adder 14.
  • a second modulo 2 adder receives the undelayed input and a copy of the input delayed by Z "2 .
  • the encoder has an output of two bits for every encoded bit.
  • this encoder in response to an input signal train can be analysed in terms of a timing diagram. From such analysis it can be determined that the encoder operates as a state machine. At each clock signal the state machine transits from one predefined state to another, and on entering a state asserts a new output as a function of the input signal.
  • transition tables and output tables can be represented by a trellis as shown in Figure 5.
  • a/bc represents as "a” the input which is 1 or 0, and "be” represents the output from the circuit.
  • Figure 5 re- represents the data in the transition and output tables.
  • the Viterbi decoding algorithm keeps a running total of a metric used to measure the "distance" or degree of mismatch between the symbol pair that was actually received and the possible symbol pairs that could have been received.
  • a simple metric will be used, namely the sum of the bit difference.
  • the symbol or bit pairs output from the convolutional encoder are, for the purposes of transmitting them in the communications channel mapped onto an appropriate symbol in the constellation diagram.
  • the convolutional encoder can output "00", “01”, “10” and “11” and hence only four symbols would be required to represent these possible outputs.
  • more complex schemes exist for both convolutional encoders and constellation diagrams but the principles exemplified here are capable of extension to the more complex schemes.
  • the symbols of the constellation diagram are mapped back to the bit sequences output by the encoder.
  • next allowable state is 00 if the input to the encoder was 0, and the received symbol would be "00".
  • the other next allowable state is 10 if the input to the encoder was 1, and the output symbol would have been 11 ; for state 01, the next allowable state is 00 if the input signal to the encoder was 0, and the received symbol would be 11.
  • the alternative allowable next state is state 10 if the input to the encoder was
  • next allowable state is 01 if the input to the encoder was 0, in which case the received symbol would be "10", whereas an alternative allowable transition would be state 11 if the input to the encoder 1, in which case the received symbol would be 01; finally for state 11, the next allowable transition is to state 01 if the input to the encoder is zero, in which case the received symbol would be 01, or to state 1 1 if the input to the encoder was 1 , in which case the received symbol would be 10.
  • Each position in the constellation diagram corresponds to one of the states in the decoding trellis (thus Figures 5 to 8 need expanding to uniquely identify eight states so as to match up with Figure 2).
  • each received symbol was assumed to lie exactly at the appropriate place for it on the constellation diagram.
  • multipath distortion provides a mechanism in which the received symbols become displaced from their ideal position in the constellation diagram.
  • the input supplied to the Viterbi decoder represents the convolution of the transmitted signal and the impulse response of the transmission path.
  • the channel impulse response can be estimated by known techniques and consequently the estimation of the channel impulse response need not be described here.
  • known techniques involve the transmission of a predefined training sequence.
  • the information content (and hence symbol sequence) is known and hence the channel state can be estimated.
  • a list of possible previous states is used to generate a set of anticipated signals which are supplied to the decoder.
  • signals undergoing multipath (or similar) distortion it is desirable to include the effects of the multipath distortion during the generation of the anticipated signals.
  • the contributions from each of the possible previous states are convolved with the channel impulse response to produce a contribution to the anticipated signal. This is normally done one state at a time. A comparison is then made between the anticipated signal and the received signal to derive a measurement of the difference between these signals.
  • h is an array of T channel impulse response taps (i.e. an array which represents quantised delays applied to the transmitted signal)
  • c is array of S ideal transmitted symbols (i.e. the symbols on the constellation diagram)
  • x is an array consisting of a path of T possible transmitted signals, the signal b that would be anticipated by this path is given by
  • This signal is compared with the received signal for each path in turn, and the signal that produces the closest match is the one that is selected.
  • the decoder keeps a running list of possible states and the symbols that would be expected when making a transition from one state to another.
  • the Viterbi decoding process inherently keeps a representation of the signal at different points in time, or as another way of looking at it, with various time delays applied.
  • a receiver having five taps and arranged to work with a transmission scheme having eight symbols it is possible for the decoder to examine all of the possible sequences of the transmitted signals.
  • each one of the eight symbols is decoded as a sequence of three bits, and the output of the decoder is a bit stream. Consequently in order to account for multipath distortion it is necessary to re-map the possible transmitted bit sequences back onto the symbols that would have been transmitted in order to encode that bit sequence.
  • the symbols are in a sequence as determined by the bit sequence.
  • the symbol sequence is then presented to the delay calculator which applies the various delays that occur in the real transmission channel, and each respective delay tap is then multiplied by the estimate of the channel response coefficients to derive a value b which corresponds to the value of the next signal (or current signal) that the receiver is expected to receive.
  • ⁇ [ ⁇ ]] represents the estimate of the 0 th transmitted symbol
  • c[ ⁇ [l]] represents the estimate of the 1 st transmitted symbol
  • the amount of computation required in a Viterbi decoder for communications is reduced by pre-calculating some of the steps. Since the value of h[a] c[x[b]] is always constant for a given tap "a" and symbol "b", two or more pre-calculated values are stored in an array which has as many dimensions as the number of steps to be calculated.
  • a demodulator where the channel state correction is implemented with five taps giving five time delay versions of the assumed transmitted sequence that, when convolved with the channel impulse response, gives rise to the received sequence of symbols.
  • the impulse response for the channel can be assumed to have been estimated.
  • the value can be pre-calculated and need only be updated if it is determined that channel's impulse response has changed.
  • the pre-calculated values can be stored in a rewritable memory 8.
  • E-GPRS equalization in a handset may implement the full trellis only between the first few taps, then a small number of paths for the next few taps then finally only one path for the last few taps.
  • the main computation effort is in the full trellis computation; then comes the small number of paths, then finally the single path.
  • the full trellis will be computed for the first two taps, two paths for the next three taps, and one path for the final two taps.
  • a lookup table of hx_01 is used to compute the full trellis: this saves two complex multiplications and a complex add, which corresponds to about 75% of the computation effort.
  • a lookup table of hx_234 is used for the next 3 taps, saving the same amount of effort for a smaller task. This saves about 15% of the computation effort.

Landscapes

  • Engineering & Computer Science (AREA)
  • Power Engineering (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Error Detection And Correction (AREA)

Abstract

L'invention concerne un récepteur dans lequel la charge de calcul pour effectuer le décodage en treillis s'effectue par un pré-calcul, pour au moins un échantillon de retard, du produit d'un signal transmis idéal et de la réponse d'un canal, pour la quantité de retard donnée. Les résultats sont stockés en mémoire de sorte à pouvoir être consultés lors du décodage en treillis.
PCT/GB2005/003042 2004-08-03 2005-08-03 Methode et appareil pour accroitre l'efficacite de calcul dans une estimation sequentielle WO2006013361A1 (fr)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
GB0417292A GB0417292D0 (en) 2004-08-03 2004-08-03 Method of and apparatus for improving computational efficiency in sequence estimation
GB0417292.0 2004-08-03

Publications (1)

Publication Number Publication Date
WO2006013361A1 true WO2006013361A1 (fr) 2006-02-09

Family

ID=32982456

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/GB2005/003042 WO2006013361A1 (fr) 2004-08-03 2005-08-03 Methode et appareil pour accroitre l'efficacite de calcul dans une estimation sequentielle

Country Status (3)

Country Link
GB (1) GB0417292D0 (fr)
TW (1) TW200620916A (fr)
WO (1) WO2006013361A1 (fr)

Citations (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5331666A (en) * 1992-06-08 1994-07-19 Ericsson Ge Mobile Communications Inc. Adaptive maximum likelihood demodulator
EP1111863A2 (fr) * 1999-12-23 2001-06-27 Lucent Technologies Inc. Procédé et dispositif de raccourcissement du chemin critique des techniques d'estimation de séquences à complexité réduite
US6381271B1 (en) * 1998-08-17 2002-04-30 Telefonaktiebolaget Lm Ericsson (Publ) Low complexity decision feedback sequence estimation
US20020126775A1 (en) * 2000-12-04 2002-09-12 Stmicroelectronics N.V. Process and device for estimating the successive values of digital symbols, in particular for the equalization of an information transmission channel in mobile telephony
WO2003041349A1 (fr) * 2001-11-09 2003-05-15 Infineon Technologies Ag Egalisation par l'algorithme de viterbi au moyen d'un ensemble de tables pour maintenir a disposition des valeurs de signaux reconstruites servant au calcul de metriques de transition
US20030118093A1 (en) * 2000-07-03 2003-06-26 Peter Bohnhoff Device and method for viterbi equalization with metric increments calculated in advance
US6707849B1 (en) * 2000-02-08 2004-03-16 Ericsson Inc. Methods, receivers and equalizers having increased computational efficiency

Patent Citations (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5331666A (en) * 1992-06-08 1994-07-19 Ericsson Ge Mobile Communications Inc. Adaptive maximum likelihood demodulator
US6381271B1 (en) * 1998-08-17 2002-04-30 Telefonaktiebolaget Lm Ericsson (Publ) Low complexity decision feedback sequence estimation
EP1111863A2 (fr) * 1999-12-23 2001-06-27 Lucent Technologies Inc. Procédé et dispositif de raccourcissement du chemin critique des techniques d'estimation de séquences à complexité réduite
US6707849B1 (en) * 2000-02-08 2004-03-16 Ericsson Inc. Methods, receivers and equalizers having increased computational efficiency
US20030118093A1 (en) * 2000-07-03 2003-06-26 Peter Bohnhoff Device and method for viterbi equalization with metric increments calculated in advance
US20020126775A1 (en) * 2000-12-04 2002-09-12 Stmicroelectronics N.V. Process and device for estimating the successive values of digital symbols, in particular for the equalization of an information transmission channel in mobile telephony
WO2003041349A1 (fr) * 2001-11-09 2003-05-15 Infineon Technologies Ag Egalisation par l'algorithme de viterbi au moyen d'un ensemble de tables pour maintenir a disposition des valeurs de signaux reconstruites servant au calcul de metriques de transition

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
DUEL-HALLEN A ET AL: "Delayed decision-feedback sequence estimation", IEEE TRANSACTIONS ON COMMUNICATIONS, IEEE SERVICE CENTER, PISCATAWAY, NJ, US, vol. 37, no. 5, May 1989 (1989-05-01), pages 428 - 436, XP000670554, ISSN: 0090-6778 *
EYUBOGLU M V ET AL: "Reduced-state sequence estimation for coded moudlation on intersymbol interference channels", IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, IEEE INC. NEW YORK, US, vol. 7, no. 6, 1 August 1989 (1989-08-01), pages 989 - 995, XP000048622, ISSN: 0733-8716 *

Also Published As

Publication number Publication date
TW200620916A (en) 2006-06-16
GB0417292D0 (en) 2004-09-08

Similar Documents

Publication Publication Date Title
US6937648B2 (en) Equalizer for communication over noisy channels
CN101106386B (zh) 时域自适应均衡器
EP0449327A2 (fr) Récepteur à diversité d'espace et à immunité contre le bruit
JP4503442B2 (ja) 判定フィードフォーワード等化器システム及び方法
JP4555403B2 (ja) ディジタル伝送装置の受信機のための状態削減シーケンス推定法によるイコライザ
JPH1075274A (ja) 軟判定復号器
US6269124B1 (en) Data transmission system, receiver, and recording medium
JP2008532354A (ja) 向上されたブロック等化を提供する無線通信装置及び関連する方法
JP2792812B2 (ja) 最尤系列推定器
JPH09121172A (ja) データ伝送装置
WO2002054645A3 (fr) Generateur emettant des decisions souples
JP2011055525A (ja) 仮想並列イコライザを備えた通信レシーバー
JP2008530906A (ja) 過去、現在及び／又は将来の自己相関マトリクスの予測値に基づいてブロック等化を実行する無線通信装置及び関連する方法
AU657103B2 (en) Receiver for a digital transmission system
WO1995015034A1 (fr) Dispositif d'estimation d'une valeur d'evaluation molle et dispositif d'estimation d'un systeme de vraisemblance maximale
US20030115061A1 (en) MPSK equalizer
JPH08307283A (ja) 最尤系列推定器及び最尤系列推定方法
US5844947A (en) Viterbi decoder with reduced metric computation
EP0508407B1 (fr) Estimation de séquence à maximum de vraisemblance, pour canaux de communication à radio mobile, changeants rapidement
JP2000315968A (ja) 適応型信号推定器
WO2006013361A1 (fr) Methode et appareil pour accroitre l'efficacite de calcul dans une estimation sequentielle
US6219388B1 (en) Digital data demodulating device for estimating channel impulse response
CN1187939C (zh) 移动无线接收器的改良的频道均衡
US7054392B2 (en) Process and device for estimating the successive values of digital symbols, in particular for the equalization of an information transmission channel in mobile telephony
EP0786872A2 (fr) Décodeur Viterbi avec calcul métrique réduit

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): AE AG AL AM AT AU AZ BA BB BG BR BW BY BZ CA CH CN CO CR CU CZ DE DK DM DZ EC EE EG ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KM KP KR KZ LC LK LR LS LT LU LV MA MD MG MK MN MW MX MZ NA NG NI NO NZ OM PG PH PL PT RO RU SC SD SE SG SK SL SM SY TJ TM TN TR TT TZ UA UG US UZ VC VN YU ZA ZM ZW

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): GM KE LS MW MZ NA SD SL SZ TZ UG ZM ZW AM AZ BY KG KZ MD RU TJ TM AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IS IT LT LU LV MC NL PL PT RO SE SI SK TR BF BJ CF CG CI CM GA GN GQ GW ML MR NE SN TD TG

WWE Wipo information: entry into national phase

Ref document number: 2007102571

Country of ref document: RU

NENP Non-entry into the national phase

Ref country code: DE

121 Ep: the epo has been informed by wipo that ep was designated in this application
122 Ep: pct application non-entry in european phase
点击 这是indexloc提供的php浏览器服务，不要输入任何密码和下载