[go: up one dir, main page]

GB2305827B - Viterbi co-processor and method of operation therefor - Google Patents

Viterbi co-processor and method of operation therefor

Info

Publication number
GB2305827B
GB2305827B GB9519995A GB9519995A GB2305827B GB 2305827 B GB2305827 B GB 2305827B GB 9519995 A GB9519995 A GB 9519995A GB 9519995 A GB9519995 A GB 9519995A GB 2305827 B GB2305827 B GB 2305827B
Authority
GB
United Kingdom
Prior art keywords
calculations
path
metric
state
pass
Prior art date
Legal status (The legal status 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 status listed.)
Expired - Fee Related
Application number
GB9519995A
Other versions
GB9519995D0 (en
GB2305827A (en
Inventor
Paul Adrian Golding
Irwin Russell Bennett
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Motorola Solutions UK Ltd
Original Assignee
Motorola Ltd
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 Motorola Ltd filed Critical Motorola Ltd
Priority to GB9519995A priority Critical patent/GB2305827B/en
Publication of GB9519995D0 publication Critical patent/GB9519995D0/en
Priority to PCT/EP1996/004160 priority patent/WO1997013327A1/en
Priority to EP96933367A priority patent/EP0855107A1/en
Priority to CN96197832A priority patent/CN1200849A/en
Priority to JP9513937A priority patent/JPH11513544A/en
Publication of GB2305827A publication Critical patent/GB2305827A/en
Application granted granted Critical
Publication of GB2305827B publication Critical patent/GB2305827B/en
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L1/00—Arrangements for detecting or preventing errors in the information received
    • H04L1/004—Arrangements for detecting or preventing errors in the information received by using forward error control
    • H04L1/0045—Arrangements at the receiver end
    • H04L1/0054—Maximum-likelihood or sequential decoding, e.g. Viterbi, Fano, ZJ algorithms
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
    • H03M13/39—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes
    • H03M13/41—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
    • H03M13/39—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes
    • H03M13/41—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors
    • H03M13/4115—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors list output Viterbi decoding
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
    • H03M13/39—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes
    • H03M13/41—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors
    • H03M13/4138—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors soft-output Viterbi algorithm based decoding, i.e. Viterbi decoding with weighted decisions
    • H03M13/4146—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors soft-output Viterbi algorithm based decoding, i.e. Viterbi decoding with weighted decisions soft-output Viterbi decoding according to Battail and Hagenauer in which the soft-output is determined using path metric differences along the maximum-likelihood path, i.e. "SOVA" decoding
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
    • H03M13/39—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes
    • H03M13/41—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors
    • H03M13/4138—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors soft-output Viterbi algorithm based decoding, i.e. Viterbi decoding with weighted decisions
    • H03M13/4146—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors soft-output Viterbi algorithm based decoding, i.e. Viterbi decoding with weighted decisions soft-output Viterbi decoding according to Battail and Hagenauer in which the soft-output is determined using path metric differences along the maximum-likelihood path, i.e. "SOVA" decoding
    • H03M13/4153—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors soft-output Viterbi algorithm based decoding, i.e. Viterbi decoding with weighted decisions soft-output Viterbi decoding according to Battail and Hagenauer in which the soft-output is determined using path metric differences along the maximum-likelihood path, i.e. "SOVA" decoding two-step SOVA decoding, i.e. the soft-output is determined by a second traceback operation after the determination of the hard decision like in the Berrou decoder
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
    • H03M13/39—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes
    • H03M13/41—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors
    • H03M13/4161—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors implementing path management
    • H03M13/4169—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors implementing path management using traceback
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/65—Purpose and implementation aspects
    • H03M13/6502—Reduction of hardware complexity or efficient processing
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/65—Purpose and implementation aspects
    • H03M13/6502—Reduction of hardware complexity or efficient processing
    • H03M13/6505—Memory efficient implementations
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L1/00—Arrangements for detecting or preventing errors in the information received
    • H04L1/004—Arrangements for detecting or preventing errors in the information received by using forward error control
    • H04L1/0045—Arrangements at the receiver end
    • H04L1/0052—Realisations of complexity reduction techniques, e.g. pipelining or use of look-up tables
    • H04L1/0053—Realisations of complexity reduction techniques, e.g. pipelining or use of look-up tables specially adapted for power saving

Landscapes

  • Physics & Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Artificial Intelligence (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Error Detection And Correction (AREA)

Abstract

The Viterbi state trellis (120) was Window Error Detection and effects two passes of a frame through the trellis (120). During a first pass, metric-difference calculations are suspended, but path metric calculations are indexed. At an identified branch, trellis data words (138-144) are recorded and associated with the branch. Upon completion of the first pass, a desired survivor path is determined and "traced-back" to its corresponding state in the identified branch using indexed path metrics, for example. The path metric corresponding to this state is nominally reloaded and, starting from that state, decoding of the frame occurs for a second pass while metric-difference (L-value) calculations are performed on the desired survivor path only, and only a single lowest L-value for the desired survivor path is recorded. This is intended to reduce memory space for the calculations and reduce power requirements. It may be used in GSM cellular communications using forward error correction.
GB9519995A 1995-09-30 1995-09-30 Viterbi co-processor and method of operation therefor Expired - Fee Related GB2305827B (en)

Priority Applications (5)

Application Number Priority Date Filing Date Title
GB9519995A GB2305827B (en) 1995-09-30 1995-09-30 Viterbi co-processor and method of operation therefor
PCT/EP1996/004160 WO1997013327A1 (en) 1995-09-30 1996-09-24 Viterbi co-processor and method of operation therefor
EP96933367A EP0855107A1 (en) 1995-09-30 1996-09-24 Viterbi co-processor and method of operation therefor
CN96197832A CN1200849A (en) 1995-09-30 1996-09-24 Viterbi co-processor and method of operation therefor
JP9513937A JPH11513544A (en) 1995-09-30 1996-09-24 Viterbi coprocessor and method

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
GB9519995A GB2305827B (en) 1995-09-30 1995-09-30 Viterbi co-processor and method of operation therefor

Publications (3)

Publication Number Publication Date
GB9519995D0 GB9519995D0 (en) 1995-12-06
GB2305827A GB2305827A (en) 1997-04-16
GB2305827B true GB2305827B (en) 2000-01-19

Family

ID=10781562

Family Applications (1)

Application Number Title Priority Date Filing Date
GB9519995A Expired - Fee Related GB2305827B (en) 1995-09-30 1995-09-30 Viterbi co-processor and method of operation therefor

Country Status (5)

Country Link
EP (1) EP0855107A1 (en)
JP (1) JPH11513544A (en)
CN (1) CN1200849A (en)
GB (1) GB2305827B (en)
WO (1) WO1997013327A1 (en)

Families Citing this family (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100190291B1 (en) * 1996-07-30 1999-06-01 윤종용 Traceback Control Unit of Viterbi Decoder
CN1154284C (en) 1997-06-13 2004-06-16 西门子公司 Source-controlled channel decoding using intra-frame correlation
FI104774B (en) * 1998-03-23 2000-03-31 Nokia Networks Oy Method and apparatus for modulation detection
FI106416B (en) 1999-02-09 2001-01-31 Nokia Mobile Phones Ltd Method and apparatus for estimating the reliability of a decoded symbol sequence
JP3374908B2 (en) 1999-05-06 2003-02-10 日本電気株式会社 Method of updating reference value in high-speed closed-loop transmission power control
DE50104995D1 (en) 2000-10-24 2005-02-03 Infineon Technologies Ag METHOD AND DEVICE FOR DECODING A SUCCESSION OF PHYSICAL SIGNALS, RELIABILITY VALUATION DETERMINATION UNIT AND VITERBI DECODING UNIT
AU2003221526A1 (en) * 2003-03-27 2004-10-18 Nokia Corporation List output viterbi decoder with blockwise acs and traceback

Family Cites Families (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE3600905A1 (en) * 1986-01-15 1987-07-16 Ant Nachrichtentech METHOD FOR DECODING BINARY SIGNALS AND VITERBI DECODERS AND APPLICATIONS
DE3725655A1 (en) * 1987-08-03 1989-02-16 Ant Nachrichtentech METHOD FOR EVALUATING BRANCH AND PATH METRICS AND ARRANGEMENT
BE1004814A3 (en) * 1991-05-08 1993-02-02 Bell Telephone Mfg Decoder.
US5408502A (en) * 1992-07-13 1995-04-18 General Instrument Corporation Apparatus and method for communicating digital data using trellis coded QAM with punctured convolutional codes
US5430768A (en) * 1994-09-21 1995-07-04 Seagate Technology, Inc. Maximum likelihood detector for a disc drive PRML read channel

Also Published As

Publication number Publication date
WO1997013327A1 (en) 1997-04-10
CN1200849A (en) 1998-12-02
GB9519995D0 (en) 1995-12-06
JPH11513544A (en) 1999-11-16
EP0855107A1 (en) 1998-07-29
GB2305827A (en) 1997-04-16

Similar Documents

Publication Publication Date Title
US7895497B2 (en) Apparatus and method using reduced memory for channel decoding in a software-defined radio system
US7191377B2 (en) Combined turbo-code/convolutional code decoder, in particular for mobile radio systems
AU762877B2 (en) Component decoder and method thereof in mobile communication system
ZA979958B (en) Soft decision output decoder for decoding convolutionally encoded codewords.
ATE26371T1 (en) DECODING ARRANGEMENT FOR ERROR CORRECTING CODES.
CA2180311A1 (en) Soft-decision receiver and decoder for digital communication
MX9710511A (en) An optimal soft-output decoder for tail-biting trellis codes.
SG46527A1 (en) Method and apparatus for reduced-coplexity viterbi-type sequence detectors
JP2001267938A (en) Map decoding using parallel-processed sliding window processing
KR20080098391A (en) MAP decoder with bidirectional sliding window architecture
EP1056212A3 (en) Viterbi decoding using single-wrong-turn correction
EP1111863A3 (en) Method and apparatus for shortening the critical path of reduced complexity sequence estimation techniques
GB2305827B (en) Viterbi co-processor and method of operation therefor
US6504882B1 (en) Add-compare-select circuit for viterbi decoder
US7669105B2 (en) Generic maximum aposteriori probability decoder for use in software-defined radio systems
JP2004343716A (en) Method for blind detection of transmission format of convolutionally encoded signal and decoder
KR950016068A (en) Digital communication system operating system
KR100336246B1 (en) Integrated circuit with digital processor and co-processor
WO2001031869A1 (en) Cache and caching method for convolutional decoders
US7979781B2 (en) Method and system for performing Viterbi decoding using a reduced trellis memory
EP0233788A3 (en) Viterbi decoder and method
EP1056213A2 (en) Decoding method and apparatus for decoding
GB2418820A (en) Blind transport format (TF) determination (BTFD) for 3G phones using maximum likelihood with reduced decoding using temporary buffers for decoded data
Engin et al. Viterbi decoding on a coprocessor architecture with vector parallelism
KR980006964A (en) Retracement device of lattice decoder

Legal Events

Date Code Title Description
PCNP Patent ceased through non-payment of renewal fee

Effective date: 20000419