WO1995018489A1 - Convolutional interleaver and deinterleaver - Google Patents

Convolutional interleaver and deinterleaver Download PDF

Info

Publication number
WO1995018489A1
WO1995018489A1 PCT/US1994/014628 US9414628W WO9518489A1 WO 1995018489 A1 WO1995018489 A1 WO 1995018489A1 US 9414628 W US9414628 W US 9414628W WO 9518489 A1 WO9518489 A1 WO 9518489A1
Authority
WO
WIPO (PCT)
Prior art keywords
column
address
deinterleaver
convolutional interleaver
memory location
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.)
Ceased
Application number
PCT/US1994/014628
Other languages
French (fr)
Inventor
Mark Fimoff
Scott F. Halozan
Raymond C. Hauge
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.)
Zenith Electronics LLC
Original Assignee
Zenith Electronics LLC
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 Zenith Electronics LLC filed Critical Zenith Electronics LLC
Priority to JP51811495A priority Critical patent/JP3169613B2/en
Priority to EP95906008A priority patent/EP0737385B1/en
Priority to KR1019960703451A priority patent/KR100208929B1/en
Priority to CA002180242A priority patent/CA2180242C/en
Priority to DE69428915T priority patent/DE69428915T2/en
Publication of WO1995018489A1 publication Critical patent/WO1995018489A1/en
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • 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/27—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 using interleaving techniques
    • H03M13/2782—Interleaver implementations, which reduce the amount of required interleaving memory
    • H03M13/2785—Interleaver using in-place interleaving, i.e. writing to and reading from the memory is performed at the same memory location
    • 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/27—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 using interleaving techniques
    • H03M13/2732—Convolutional interleaver; Interleavers using shift-registers or delay lines like, e.g. Ramsey type interleaver
    • 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/27—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 using interleaving techniques
    • H03M13/276—Interleaving address generation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/85—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using pre-processing or post-processing specially adapted for video compression
    • H04N19/89—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using pre-processing or post-processing specially adapted for video compression involving methods or arrangements for detection of transmission errors at the decoder

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Theoretical Computer Science (AREA)
  • Multimedia (AREA)
  • Signal Processing (AREA)
  • Error Detection And Correction (AREA)
  • Detection And Correction Of Errors (AREA)
  • Digital Transmission Methods That Use Modulated Carrier Waves (AREA)
  • Optical Record Carriers And Manufacture Thereof (AREA)

Abstract

A convolutional interleaver or deinterleaver comprises an address signal generator for repeatedly generating [(B-1)N/2] + 1 sequences of address signals, where B is a desired interleave depth and N is a value equal to or greater than the number of data bytes in an R-S block of the data stream. Each of the sequences corresponds to a respective row of a B column matrix, the first column of which comprises [(B-1)N/2] + 1 consecutively numbered values. Each remaining column comprises the preceding column rotated by an integer multiple of N/B. The address signals are applied to a memory having [(B-1)N/2] + 1 storage locations for reading the data stored at the address memory location and then writing the current data byte to the same memory location.
PCT/US1994/014628 1993-12-29 1994-12-15 Convolutional interleaver and deinterleaver Ceased WO1995018489A1 (en)

Priority Applications (5)

Application Number Priority Date Filing Date Title
JP51811495A JP3169613B2 (en) 1993-12-29 1994-12-15 Renormalized interleaver and deinterleaver
EP95906008A EP0737385B1 (en) 1993-12-29 1994-12-15 Convolutional interleaver and deinterleaver
KR1019960703451A KR100208929B1 (en) 1993-12-29 1994-12-15 Convolutional interleaver and deinterleaver
CA002180242A CA2180242C (en) 1993-12-29 1994-12-15 Convolutional interleaver and deinterleaver
DE69428915T DE69428915T2 (en) 1993-12-29 1994-12-15 DEVICE FOR FOLDING AND DETACHING

Applications Claiming Priority (4)

Application Number Priority Date Filing Date Title
US17532593A 1993-12-29 1993-12-29
US08/175,325 1993-12-29
US08/315,153 1994-09-29
US08/315,153 US5572532A (en) 1993-12-29 1994-09-29 Convolutional interleaver and deinterleaver

Publications (1)

Publication Number Publication Date
WO1995018489A1 true WO1995018489A1 (en) 1995-07-06

Family

ID=26871101

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/US1994/014628 Ceased WO1995018489A1 (en) 1993-12-29 1994-12-15 Convolutional interleaver and deinterleaver

Country Status (9)

Country Link
US (1) US5572532A (en)
EP (1) EP0737385B1 (en)
JP (1) JP3169613B2 (en)
KR (1) KR100208929B1 (en)
CN (1) CN1083642C (en)
CA (1) CA2180242C (en)
DE (1) DE69428915T2 (en)
TW (1) TW311311B (en)
WO (1) WO1995018489A1 (en)

Cited By (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0759665A1 (en) * 1995-08-21 1997-02-26 ALCATEL BELL Naamloze Vennootschap Method for interleaving data frames, forward error correcting device and modulator including such a device
WO1997037434A1 (en) * 1996-03-29 1997-10-09 Amati Communications Corporation Convolutional interleaving with reduced memory requirements and address generator therefor
GB2315002A (en) * 1996-07-01 1998-01-14 Daewoo Electronics Co Ltd Convolutional interleaver and method for generating address
WO2000008771A1 (en) * 1998-08-06 2000-02-17 Qualcomm Incorporated Method and apparatus for rotating modulation symbol indices
WO2000027035A1 (en) * 1998-10-30 2000-05-11 Broadcom Corporation Generalized convolutional interleaver/deinterleaver
EP1039646A1 (en) * 1999-03-05 2000-09-27 Mitsubishi Electric France Interleaver device and method for interleaving a data set
WO2001069794A1 (en) * 2000-03-17 2001-09-20 Matsushita Electric Industrial Co., Ltd. Interleave address generator
KR100531387B1 (en) * 1997-05-30 2006-01-27 가부시끼가이샤 도시바 Multi-carrier transmission interleaving device and method
US7600164B2 (en) 2004-12-17 2009-10-06 Telefonaktiebolaget Lm Ericsson (Publ) Interleaving/de-interleaving using compressed bit-mapping sequences
EP1553711A3 (en) * 2003-12-30 2013-03-20 Samsung Electronics Co., Ltd. Deinterleaving device for digital broadcast receivers having a downsized deinterleaver memory and deinterleaving method thereof

Families Citing this family (44)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5771081A (en) * 1994-02-28 1998-06-23 Korea Telecommunication Authority Bit system for transmitting digital video data
JP3614907B2 (en) * 1994-12-28 2005-01-26 株式会社東芝 Data retransmission control method and data retransmission control system
US5898710A (en) * 1995-06-06 1999-04-27 Globespan Technologies, Inc. Implied interleaving, a family of systematic interleavers and deinterleavers
US5719875A (en) * 1996-06-11 1998-02-17 Lucent Technologies Inc. Systematic convolution interleavers and deinterleavers
US6173330B1 (en) * 1996-09-17 2001-01-09 Motorola, Inc. Delivery and acquisition of data segments with optimized inter-arrival time
US5912898A (en) * 1997-02-27 1999-06-15 Integrated Device Technology, Inc. Convolutional interleaver/de-interleaver
JPH10303854A (en) * 1997-04-23 1998-11-13 Matsushita Electric Ind Co Ltd Deinterleave device
US6826181B1 (en) * 1997-05-13 2004-11-30 Matsushita Electric Industrial Co., Ltd. Packet transmitter
KR100237745B1 (en) * 1997-05-23 2000-01-15 김영환 Memory address generator of rotary interleaver / deinterleaver and method
US6055277A (en) * 1997-05-29 2000-04-25 Trw Docket No. Communication system for broadcasting to mobile users
KR19990003242A (en) 1997-06-25 1999-01-15 윤종용 Structural Punched Convolutional Codes and Decoders
US5938763A (en) * 1997-08-06 1999-08-17 Zenith Electronics Corporation System for transposing data from column order to row order
JP3295372B2 (en) * 1998-04-22 2002-06-24 日本プレシジョン・サーキッツ株式会社 Deinterleave device
US6178530B1 (en) 1998-04-24 2001-01-23 Lucent Technologies Inc. Addressing scheme for convolutional interleaver/de-interleaver
US6411654B1 (en) 1998-04-27 2002-06-25 Matsushita Electric Industrial Co., Ltd. Convolutional interleaver, convolutional deinterleaver, convolutional interleaving method, and convolutional deinterleaving method
KR100306282B1 (en) * 1998-12-10 2001-11-02 윤종용 Apparatus and for interleaving and deinterleaving frame date in communication system
US6536001B1 (en) * 1999-03-11 2003-03-18 Globespanvirata, Inc. Circuit and method for convolutional interleaving using a single modulo operation
US6314534B1 (en) * 1999-03-31 2001-11-06 Qualcomm Incorporated Generalized address generation for bit reversed random interleaving
TW424227B (en) * 1999-04-08 2001-03-01 Via Tech Inc Signal decoding device and method thereof
AU4207800A (en) * 1999-04-09 2000-11-14 Sony Electronics Inc. Interleavers and de-interleavers
US6543013B1 (en) * 1999-04-14 2003-04-01 Nortel Networks Limited Intra-row permutation for turbo code
US6782056B1 (en) * 1999-08-03 2004-08-24 Sony Corporation DSS packet reordering function
KR100645730B1 (en) * 1999-12-30 2006-11-13 주식회사 케이티 Interleaving Method Using Magic Matrix
US7770010B2 (en) * 2000-09-18 2010-08-03 Wideband Semiconductors Inc. Dynamically configurable interleaver scheme using at least one dynamically changeable interleaving parameter
US6563436B2 (en) 2001-09-24 2003-05-13 Zenith Electronics Corporation Kerdock coding and decoding system for map data
US6924753B2 (en) * 2001-09-24 2005-08-02 Zenith Electronics Corporation Robust system for transmitting and receiving map data
US6927708B2 (en) * 2001-09-24 2005-08-09 Zenith Electronics Corporation Mapping system for transmission and reception of multiple data types
US7586993B2 (en) * 2001-12-06 2009-09-08 Texas Instruments Incorporated Interleaver memory selectably receiving PN or counter chain read address
JP2006501724A (en) * 2002-09-27 2006-01-12 アイビキュイティ・デジタル・コーポレイション Method and apparatus for interleaving signal bits in a digital audio broadcasting system
RU2265960C2 (en) * 2003-06-16 2005-12-10 Федеральное государственное унитарное предприятие "Калужский научно-исследовательский институт телемеханических устройств" Method for transferring information with use of adaptive alternation
US8077743B2 (en) * 2003-11-18 2011-12-13 Qualcomm Incorporated Method and apparatus for offset interleaving of vocoder frames
DE60322550D1 (en) * 2003-12-09 2008-09-11 St Microelectronics Nv Method and apparatus for deinterleaving successive sequences of interlaced sample data
US7343530B2 (en) * 2004-02-10 2008-03-11 Samsung Electronics Co., Ltd. Turbo decoder and turbo interleaver
US20060245505A1 (en) * 2005-05-02 2006-11-02 Limberg Allen L Digital television signals using linear block coding
NZ563210A (en) * 2005-05-12 2010-11-26 Qualcomm Inc Apparatus and method for channel interleaving in communications system
US7685495B2 (en) * 2005-05-12 2010-03-23 Qualcomm Incorporated Apparatus and method for channel interleaving in communications system
US7657818B2 (en) * 2005-06-22 2010-02-02 Adaptive Spectrum And Signal Alignment, Inc. Dynamic minimum-memory interleaving
TWI269535B (en) * 2005-09-13 2006-12-21 Sunplus Technology Co Ltd Convolutional interleaving and de-interleaving circuit and method
CN101682466A (en) * 2007-05-16 2010-03-24 汤姆森特许公司 Apparatus and method for encoding and decoding signals
CN107070585B (en) 2007-10-15 2021-05-04 交互数字Ce专利控股公司 Apparatus and method for communicating burst mode activity
US8908773B2 (en) 2007-10-15 2014-12-09 Thomson Licensing Apparatus and method for encoding and decoding signals
US8799750B1 (en) * 2011-05-09 2014-08-05 Xilinx, Inc. Convolutional interleaver for bursty memory access
CN102832954B (en) * 2012-09-17 2015-01-28 华中科技大学 Turbo code iterative decoding stopping method based on soft information average minimum value
US10176551B2 (en) * 2017-04-27 2019-01-08 Apple Inc. Configurable convolution engine for interleaved channel data

Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4394642A (en) * 1981-09-21 1983-07-19 Sperry Corporation Apparatus for interleaving and de-interleaving data
EP0235477A1 (en) * 1985-12-23 1987-09-09 Thomson-Csf Jamming resistant method and apparatus for radio transmission of coded information
EP0370444A1 (en) * 1988-11-25 1990-05-30 Alcatel Telspace Interleaving method for a digital transmission device
EP0405673A1 (en) * 1989-06-28 1991-01-02 Koninklijke Philips Electronics N.V. Device for buffering data for the duration of cyclically recurrent buffer periods
US5042033A (en) * 1989-06-05 1991-08-20 Canadian Marconi Corporation RAM-implemented convolutional interleaver
EP0467717A2 (en) * 1990-07-20 1992-01-22 Matsushita Electric Industrial Co., Ltd. Data shuffling apparatus

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5241563A (en) * 1992-08-10 1993-08-31 General Instrument Corporation Method and apparatus for communicating interleaved data

Patent Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4394642A (en) * 1981-09-21 1983-07-19 Sperry Corporation Apparatus for interleaving and de-interleaving data
EP0235477A1 (en) * 1985-12-23 1987-09-09 Thomson-Csf Jamming resistant method and apparatus for radio transmission of coded information
EP0370444A1 (en) * 1988-11-25 1990-05-30 Alcatel Telspace Interleaving method for a digital transmission device
US5042033A (en) * 1989-06-05 1991-08-20 Canadian Marconi Corporation RAM-implemented convolutional interleaver
EP0405673A1 (en) * 1989-06-28 1991-01-02 Koninklijke Philips Electronics N.V. Device for buffering data for the duration of cyclically recurrent buffer periods
EP0467717A2 (en) * 1990-07-20 1992-01-22 Matsushita Electric Industrial Co., Ltd. Data shuffling apparatus

Non-Patent Citations (3)

* Cited by examiner, † Cited by third party
Title
CHI D T: "A NEW BLOCK HELICAL INTERLEAVER", MILCOM 92, COMMUNICATIONS - FUSING COMMAND, CONTROL AND INTELLIGENCE, SAN DIEGO, OCT. 11 - 14, 1992, vol. 2/3, INSTITUTE OF ELECTRICAL AND ELECTRONICS ENGINEERS, pages 799 - 804, XP000346692 *
DARMON ET AL.: "A new pseudo-random interleaving for antijamming applications", MILCOM 89, BRIDGING THE GAP: INTEROPERABILITY, SURVIVABILITY, SECURITY, BOSTON, OCT. 15 - 18 1989, IEEE, vol. 1/3, pages 6 - 10 *
G.C.CLARK, J.B.CAIN: "Error correction coding for digital communication", NEW YORK *

Cited By (19)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6202178B1 (en) 1995-08-21 2001-03-13 Alcatel N.V. Complementary methods for interleaving and deinterleaving data frames and corresponding forward error correcting devices in a transmitter and receiver
US5907560A (en) * 1995-08-21 1999-05-25 Alcatel N.V. Method for interleaving data frames, forward error correcting device and modulator including such a device
EP0759665A1 (en) * 1995-08-21 1997-02-26 ALCATEL BELL Naamloze Vennootschap Method for interleaving data frames, forward error correcting device and modulator including such a device
WO1997037434A1 (en) * 1996-03-29 1997-10-09 Amati Communications Corporation Convolutional interleaving with reduced memory requirements and address generator therefor
US5764649A (en) * 1996-03-29 1998-06-09 Amati Communications Corporation Efficient address generation for convolutional interleaving using a minimal amount of memory
GB2315002A (en) * 1996-07-01 1998-01-14 Daewoo Electronics Co Ltd Convolutional interleaver and method for generating address
US6035427A (en) * 1996-07-01 2000-03-07 Daewoo Electronics Co., Ltd. Convolutional interleaver and method for generating memory address therefor
GB2315002B (en) * 1996-07-01 2001-01-10 Daewoo Electronics Co Ltd Convolutional interleaver and method for generating address therefor
KR100531387B1 (en) * 1997-05-30 2006-01-27 가부시끼가이샤 도시바 Multi-carrier transmission interleaving device and method
WO2000008771A1 (en) * 1998-08-06 2000-02-17 Qualcomm Incorporated Method and apparatus for rotating modulation symbol indices
US6546520B1 (en) 1998-10-30 2003-04-08 Broadcom Corporation Generalized convolutional interleaver/deinterleaver
US6697975B2 (en) 1998-10-30 2004-02-24 Broadcom Corporation Generalized convolutional interleaver/deinterleaver
WO2000027035A1 (en) * 1998-10-30 2000-05-11 Broadcom Corporation Generalized convolutional interleaver/deinterleaver
US7024597B2 (en) 1998-10-30 2006-04-04 Broadcom Corporation Generalized convolutional interleaver/deinterleaver
EP1039646A1 (en) * 1999-03-05 2000-09-27 Mitsubishi Electric France Interleaver device and method for interleaving a data set
US6701467B1 (en) 1999-03-05 2004-03-02 Mitsubishi Electric Telecom Europe Interleaver device and method for interleaving a data set
WO2001069794A1 (en) * 2000-03-17 2001-09-20 Matsushita Electric Industrial Co., Ltd. Interleave address generator
EP1553711A3 (en) * 2003-12-30 2013-03-20 Samsung Electronics Co., Ltd. Deinterleaving device for digital broadcast receivers having a downsized deinterleaver memory and deinterleaving method thereof
US7600164B2 (en) 2004-12-17 2009-10-06 Telefonaktiebolaget Lm Ericsson (Publ) Interleaving/de-interleaving using compressed bit-mapping sequences

Also Published As

Publication number Publication date
US5572532A (en) 1996-11-05
CN1141101A (en) 1997-01-22
DE69428915D1 (en) 2001-12-06
KR100208929B1 (en) 1999-07-15
JPH09507352A (en) 1997-07-22
EP0737385B1 (en) 2001-10-31
TW311311B (en) 1997-07-21
CN1083642C (en) 2002-04-24
JP3169613B2 (en) 2001-05-28
EP0737385A1 (en) 1996-10-16
CA2180242C (en) 2000-06-27
DE69428915T2 (en) 2002-04-25

Similar Documents

Publication Publication Date Title
EP0737385A1 (en) Convolutional interleaver and deinterleaver
EP0681373B1 (en) Convolutional interleaver with reduced memory requirements and address generator therefor
US5745497A (en) Convolutional interleaving/DE-interleaving method and apparatus for data transmission
US4306305A (en) PCM Signal transmitting system with error detecting and correcting capability
CN1381095B (en) Efficient Implementation of TURBO Code Interleaver Recommended for Third Code Division Multiple Access
CA2337918A1 (en) Turbo interleaving apparatus and method
JP4955049B2 (en) Block interleaving for turbo coding
EP0954109B1 (en) Convolutional interleaver, convolutional deinterleaver, convolutional interleaving method, and convolutional deinterleaving method
RU2007125429A (en) TURBODECODER USING LINEAR CONFIGURANT SEQUENCES
US7032138B2 (en) Generalized convolutional interleaver/de-interleaver
US6178530B1 (en) Addressing scheme for convolutional interleaver/de-interleaver
WO2002019537A1 (en) Interleaving apparatus
GB2317540A (en) Base-band interleaver for code division multiple access mobile telecommunicatio system
CA2140536A1 (en) Apparatus and Method for Producing an Analog Output Signal from a Digital Input Word
US5276827A (en) Data buffer for the duration of cyclically recurrent buffer periods
US5978883A (en) Block interleaving and deinterleaving method and device therefor
WO2000004645A1 (en) De-interleave circuit
CN1614898B (en) Turbo code encoder and encoding method
US20050050284A1 (en) System and method for interleaving data in a communications device
US6329935B1 (en) Temporally separating and re-organizing data using two-stage interleaving and de-interleaving
GB2059723A (en) Interleavers for digital data signals
KR0141240B1 (en) Memory device of error correction
KR100556469B1 (en) Interleaver and deinterleaver
KR19980023731A (en) Address generation method of convolutional interleaver / deinterleaver and static RAM using static RAM
JPS5758280A (en) Method for making memory address

Legal Events

Date Code Title Description
WWE Wipo information: entry into national phase

Ref document number: 94194756.4

Country of ref document: CN

AK Designated states

Kind code of ref document: A1

Designated state(s): CA CN JP KR

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): AT BE CH DE DK ES FR GB GR IE IT LU MC NL PT SE

121 Ep: the epo has been informed by wipo that ep was designated in this application
DFPE Request for preliminary examination filed prior to expiration of 19th month from priority date (pct application filed before 20040101)
WWE Wipo information: entry into national phase

Ref document number: 1995906008

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 2180242

Country of ref document: CA

WWP Wipo information: published in national office

Ref document number: 1995906008

Country of ref document: EP

WWG Wipo information: grant in national office

Ref document number: 1995906008

Country of ref document: EP