CN1306348A - 对长度可变的数据分组进行有效交织的方法 - Google Patents

对长度可变的数据分组进行有效交织的方法 Download PDF

Info

Publication number
CN1306348A
CN1306348A CN00137726A CN00137726A CN1306348A CN 1306348 A CN1306348 A CN 1306348A CN 00137726 A CN00137726 A CN 00137726A CN 00137726 A CN00137726 A CN 00137726A CN 1306348 A CN1306348 A CN 1306348A
Authority
CN
China
Prior art keywords
interleaver
size
block
packet
tot
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.)
Pending
Application number
CN00137726A
Other languages
English (en)
Inventor
A·雅基尔
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.)
Texas Instruments Inc
Original Assignee
Texas Instruments Inc
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 Texas Instruments Inc filed Critical Texas Instruments Inc
Publication of CN1306348A publication Critical patent/CN1306348A/zh
Pending 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/2789—Interleaver providing variable interleaving, e.g. variable block sizes
    • 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/2703—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 the interleaver involving at least two directions
    • H03M13/2707—Simple row-column interleaver, i.e. pure block interleaving

Landscapes

  • Physics & Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Error Detection And Correction (AREA)
  • Detection And Prevention Of Errors In Transmission (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Communication Control (AREA)

Abstract

提供了一种对长度可变的数据分组进行有效交织的方法。在数据分组网络中,当交织器的块大小固定且小于数据分组大小时,对长度可变数据分组的块交织效率很差。对于某些数据分组长度,最后一块的剩余单元数(即、字节或码元)非常少。本发明提供了一种为预选数据分组长度和预选交织器宽度计算最佳交织器块大小的方法。使块大小最大,同时使其大小几乎相等。

Description

对长度可变的数据分组进行有效交织的方法
本发明涉及数字通信信道，尤其涉及一种对长度可变的数据分组进行有效交织的方法。
在许多通信信道中，差错以突发方式出现，即单个差错事件具有不止一个差错数据单元(位、字节、码元或其它单元)。突发差错因各种原因而产生，原因有信道中的突发噪声，维特比解码器输出中的突发差错，以及其它形式。因为大多数解码器不能有效地处理许多相邻的差错，所以通常不希望有突发差错。交织器是一种通过对数据单元的置换将来自一个脉冲串的差错分散成分立的多个“单”差错的器件。例如，当使用分组编码(诸如，Reed-solomon)时，交织器可以在几个码字之间分散突发差错，从而放宽对该码的纠错要求。
一种非常普通而简单的交织器是块交织器。在此交织器中，将数据单元(位、字节、码元或其它单元)放在二维表的行方向，然后按表的列方向读取。块的大小(行数乘以列数)一般受交织器存储资源的限制。
在数据分组网络中，通过通信信道传送长度可变的数据分组。数据分组的大小通常大于块的大小。在此情况下，将数据分组分成许多段，段的大小小于或等于交织器块的大小。然后对每段分别交织。一种寻常的分段方式是使最后一段以外的所有分段都等于交织器块的大小。于是，最后一段将小于块的大小。此方法的缺点是，对于某些数据分组长度来说，最后一段会非常小。这将导致交织器的性能很差。
本发明提供了一种用于对长度可变的数据分组进行有效交织的方法。在数据分组网络中，当交织器的块大小固定且小于数据分组大小时，对长度可变数据分组的块交织效率很差。原因是，对于某些数据分组长度，最后一块的剩余单元数(即、字节或码元)非常少。
本发明的方法可以为已知的数据分组长度(可变)和已知的(或选定的)交织器宽度计算最佳的交织器块大小。
交织器是一种通过对数据分组中的数据单元进行排列将来自一个脉冲串的差错分散成分立的多个“单”差错的器件。例如，当使用分组编码(诸如，Reed-solomon)时，交织器可以在几个码字之间分散突发差错，从而放宽对该码的纠错要求。
一种非常普通而简单的交织器是块交织器。在此交织器中，将数据单元(位、字节、码元或其它单元)放在二维表的行方向，然后按表的列方向读取。块的大小(行数乘以列数)一般受交织器存储资源的限制。
在数据分组网络中，通过通信信道传送长度可变的数据分组。数据分组的大小通常大于块的大小。在此情况下，将数据分组分成许多段，段的大小小于或等于交织器块的大小。然后对每段分别交织。一种寻常的分段方式是使最后一段以外的所有分段都等于交织器块的大小。于是，最后一段将小于块的大小。此方法的缺点是，对于某些数据分组长度来说，最后一段会非常小。这将导致交织器的性能很差。
计算块大小更有效于仅仅挑选块大小并让尾部(最后一块)为任意获得的大小，其理由如下：一个块的脉冲串容限(即可以攻击块的最长噪声脉冲串，由此最长噪声脉冲串仍可以恢复数据)是T*I字节，其中T是Reed-Solomon(RS)校正因数，而I是块的交织深度。一个数据分组的脉冲串容限由其“最弱”的块，即交织深度最小的块决定。因此，希望最后一块的交织深度不太小(可能是1)。这可以用本发明的方法来实现。
本发明计算数据分组的各段大小，使得所有分段的大小都几乎相等，并仍然尽可能的大。列的数目是已知的或者固定的，并且最好等于码字长度。使用公式计算每段的行数，它是数据分组长度、码字长度和最大块大小的函数。
本发明提供了一种对给定数据分组长度计算最佳交织器块大小并使交织器块大小最大的简单计算方法。也就是说，本发明是将数据分散到大致相等的交织器块中，而不是具有几个大小固定的块以及一个位于尾部的小块，且小块包含少量的数据(例如，较小的交织深度)，因此本发明可以使脉冲串噪声容限最大。
在本发明的公式中使用了以下符号：
用单元表示的总数据分组长度(例如，位、字节、码元等)：Nf
交织器宽度(一般是码字长度)：Nr
最大块大小(单元数)：Br数据分组中交织器的总行数：Itot 0=ceil(Nf/Nr)，
其中“ceil(x)”是一函数，其值为沿正无限大方向最接近x的整数。
每段的最大行数(使得交织器块不超过Br)：Ir,max=floor(Br/Nr)，
其中“floor(x)”是一函数，其值为沿负无限大方向最接近x的整数。
分段数：Ns 0=ceil(Itot/Ir,max)。
于是，对于一个分段m，用于计算最大行数Ir m的公式是：
    m=1,…,Ns 0：
    Ir m=ceil(Itot (m-1)/Ns (m-1))
    Ns m=Ns (m-1)-l
    Itot m=Itot (m-1)-Ir m
使用此公式的一个例子是：
    Nf=2100,Nr=200,Br=2048，
    Itot 0=ceil(Nf/Nr)=11
    Ir,max=floor(Br/Nr)=10
    Ns 0=ceil(Itot/Ir,max)=2
    Ir 1=ceil(Itot 0/Ns 0)=6
    Ns 1=Ns 0-1=1
    Itot 1=Itot 0-Ir 1=5
    Ir 2=ceil(Itot 1/Ns 1)=5
    Ns 2=Ns 1-1=0
    Itot 2=Itot 1-Ir 2=0
在此例中，已获得了最佳分段。也就是说，对于此例，计算得到均具有5行的两个块(交织深度为5)。尽管选择了最大块大小Br，但这些公式还可以用来优化块大小，或者可以使用几种块大小并选择一个具有最佳(最大)交织深度进行使用。
以下是另一个公式。此公式提供相等的段大小，但次序不同。
同样使用先前的符号：其中
数据分组长度         Nf
码字长度             Nr
最大块大小           Br
交织器总行数         Itot 0=ceil(Nf/Nr)
每段的最大行数       Ir,max=floor(Br/Nr)
分段数               Ns 0=ceil(Itot 0/Ir,max)
第一块的交织深度          Ir 1=ceil(Irot 0/Ns 0)深度为Ir 1的块的数目       M=Ns 0·(Ir 1+1)-Itot 0于是，对于分段i，用于计算最大行数Ir (i)的公式为：(i=1,…,Ns 0)：
Figure A0013772600061
数据分组由Ns 0个交织段(块)组成，每段的宽度(列数)为Nr。最前面的M个分段的深度(行数)为Ir 1。剩余分段的深度为Ir 1+1。
使用此公式的例子如下：
    Nf=2100，Nr=200，Br=2048，
    Itot 0=ceil(Nf/Nr)=11
    Ir,max=floor(Br/Nr)=10
    Ns 0=ceil(Itot/Ir,max)=2
    Ir 1=floor(Itot 0/Ns 0)=5
    M=Ns 0-(Itot 0-Ns 0·Ir 1)=1
此例的结果是：
    Ir 1=5,Ir 2=6
也就是说，在此例中，计算得到两个块，一块具有5行，另一块具有6行。同样，可以对块大小进行优化。用类似的方式可以产生其它公式，用于计算一给定数据分组长度的交织器块大小，同时使块大小最大。
本发明可以用软件、硬件或软件与硬件的组合来实现。对于本领域的熟练技术人员来说，阅读了上述对本发明的几个特定实施例之后，很容易进行各种改变、修改和改进。这种根据本申请揭示内容为显而易见的改变、修改和改进是本说明书的一部分，尽管没有在此表述，并且它们落在本发明的精神和范围内。因此，上述描述只是举例，没有限制作用。本发明只被后附权利要求及其等效物的限制。

Claims (5)

1．一种为具有已知长度的数据分组计算交织器最佳块大小的方法，其特征在于，包括以下步骤：
使块大小最大，同时使所述块的所述大小大致相等。
2．如权利要求1所述的方法，其特征在于，还包括：
选择交织器宽度等于码字长度。
3．一种用于数据分组的交织器，其特征在于，包括：
输入电路，用于为所述数据分组提供至少一个长度；
存储器，用于存储数据分组信息；
处理器，用于根据所述数据分组信息确定最大块大小；和
输出电路，用于提供交织块中的所述数据分组信息。
4．如权利要求3所述的交织器，其特征在于，所述处理器确定所述块的所述最大尺寸，以便每个所述块的大小大致相等。
5．一种种具有已知长度的数据分组计算交织器最佳块大小的方法，其特征在于，包括以下步骤：
首先，提供以下数据：
提供用单元表示的总数据分组长度(例如，位、字节、码元等)，用Nf表示；
提供交织器宽度，用Nr表示；
提供用单元表示的最大块大小，用Br表示；
提供所述数据分组中交织器的总行数，用Itot 0=ceil(Nf/Nr)表示；
其中“ceil(x)”是一函数，其值为沿正无限大方向最接近x的整数；
提供每段的最大行数，使得交织器块不超过Br，用Ir,max=floor(Br/Nr)表示，其中“floor(x)”是一函数，其值为沿负无限大方向最接近x的整数；
提供一个分段数目，用Ns 0=ceil(Itot/Ir,max)表示；以及
其次，用以下方式处理所述数据：
对于一个分段m，按以下公式确定最大行数Ir m：
    m=1,…,Ns 0：
    Ir m=ceil(Itot (m-1)/Ns (m-1))
    Ns m=Ns (m-1)-1
    Itot m=Itot (m-1)-Ir m
CN00137726A 1999-12-28 2000-12-27 对长度可变的数据分组进行有效交织的方法 Pending CN1306348A (zh)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US09/473,155 US6337642B1 (en) 1999-12-28 1999-12-28 Method for efficient interleaving of variable length packets with maximized block size
US09/473,155 1999-12-28

Publications (1)

Publication Number Publication Date
CN1306348A true CN1306348A (zh) 2001-08-01

Family

ID=23878429

Family Applications (1)

Application Number Title Priority Date Filing Date
CN00137726A Pending CN1306348A (zh) 1999-12-28 2000-12-27 对长度可变的数据分组进行有效交织的方法

Country Status (4)

Country Link
US (1) US6337642B1 (zh)
EP (1) EP1113581A3 (zh)
JP (1) JP2001217815A (zh)
CN (1) CN1306348A (zh)

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN102113260A (zh) * 2008-06-06 2011-06-29 马克西姆综合产品公司 用于实现时间和频率分集的具有可配置大小的块交织方案
CN106134086A (zh) * 2014-03-14 2016-11-16 三星电子株式会社 用于控制交织深度的方法和设备
CN113890546A (zh) * 2021-12-06 2022-01-04 成都星联芯通科技有限公司 交织器配置方法、装置、电子设备及计算机可读存储介质

Families Citing this family (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE10219700C1 (de) * 2002-05-02 2003-09-18 Astrium Gmbh Verfahren zum Interleaving von Daten
EP1953921B1 (en) * 2007-02-05 2012-11-21 Alcatel Lucent A method for interleaving bits, a base station, a user terminal and a communication network therefor
WO2008097001A1 (en) * 2007-02-05 2008-08-14 Samsung Electronics Co., Ltd. Method and apparatus for transmitting/receiving variable-sized packet in a mobile communication system
US8418023B2 (en) 2007-05-01 2013-04-09 The Texas A&M University System Low density parity check decoder for irregular LDPC codes
US7911364B1 (en) 2007-09-04 2011-03-22 Marvell International Ltd. Interleaver for turbo equalization
US8296624B2 (en) * 2009-06-30 2012-10-23 Comcast Cable Communications, Llc Variable interleave data transmission
WO2015137712A1 (en) 2014-03-14 2015-09-17 Samsung Electronics Co., Ltd. Method and apparatus for controlling interleaving depth
US10348466B2 (en) * 2015-11-03 2019-07-09 Qualcomm Incorporated Transport block segmentation and signaling

Family Cites Families (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5200864A (en) * 1989-06-28 1993-04-06 International Business Machines Corporation Combining small records into a single record block for recording on a record media
JP3186413B2 (ja) * 1994-04-01 2001-07-11 ソニー株式会社 データ圧縮符号化方法、データ圧縮符号化装置及びデータ記録媒体
US6043763A (en) * 1998-03-12 2000-03-28 Liquid Audio, Inc. Lossless data compression with low complexity

Cited By (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN102113260A (zh) * 2008-06-06 2011-06-29 马克西姆综合产品公司 用于实现时间和频率分集的具有可配置大小的块交织方案
CN102113260B (zh) * 2008-06-06 2013-09-25 马克西姆综合产品公司 用于实现时间和频率分集的具有可配置大小的块交织方案
CN106134086A (zh) * 2014-03-14 2016-11-16 三星电子株式会社 用于控制交织深度的方法和设备
CN106134086B (zh) * 2014-03-14 2020-02-28 三星电子株式会社 用于控制交织深度的方法和设备
CN113890546A (zh) * 2021-12-06 2022-01-04 成都星联芯通科技有限公司 交织器配置方法、装置、电子设备及计算机可读存储介质
CN113890546B (zh) * 2021-12-06 2022-03-04 成都星联芯通科技有限公司 交织器配置方法、装置、电子设备及计算机可读存储介质

Also Published As

Publication number Publication date
JP2001217815A (ja) 2001-08-10
EP1113581A3 (en) 2003-10-15
EP1113581A2 (en) 2001-07-04
US6337642B1 (en) 2002-01-08

Similar Documents

Publication Publication Date Title
CN1133277C (zh) 通信系统中具有串行级联结构的编码器/解码器
CN1187903C (zh) 数据传输的速率匹配方法和装置
CN1122371C (zh) 用于通信系统的交织/解交织设备和方法
CN1202625C (zh) 利用线性同余序列的turbo码交织器
CN1345485A (zh) 二维交织设备及方法
CN1366739A (zh) 被快速(Turbo)编码了的代码序列的译码方法及译码装置
KR100480264B1 (ko) 통신시스템에서 인터리버 및 인터리빙 방법
CN1898874A (zh) 具有子块处理和基于子块的停止标准的siso解码器
CN1179651A (zh) 产生地址的卷积交错器及其方法
CN1306348A (zh) 对长度可变的数据分组进行有效交织的方法
JP3987553B2 (ja) 通信システムでインタリービングされたデータストリームのデインタリービング方法及び装置
CN1534879A (zh) 级联卷积和分组编码信号的解码装置和方法
CN1568577A (zh) 特播解码装置和方法
CN1183687C (zh) Turbo码编码器及编码方法
CN1349357A (zh) 在移动通信系统中执行特博解码的方法
CN1575547A (zh) 涡轮解码器系统中的可靠性值的非线性缩放
CN1147169C (zh) 用于Turbo码的解码方法和解码器
CN1323462A (zh) 用于最大后验概率解码器的存储器体系结构
JP2024053039A5 (zh)
CN1198416C (zh) 一种实现w－cdma系统中turbo编码交织的方法和装置
CN115765918A (zh) 一种数据交织方法及数据交织装置
CN1702976A (zh) 一种用于通信系统的数据交织与解交织方法
CN1414707A (zh) 用于降低乘积码译码所需存储量和复杂度的方法
CN1330467A (zh) 串行回溯的最大似然解码方法及其使用该方法的解码器
JP3896841B2 (ja) インターリーブ処理方法及びインターリーブ処理装置

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
C02 Deemed withdrawal of patent application after publication (patent law 2001)
WD01 Invention patent application deemed withdrawn after publication