CN1237291A - 使用可变长度编码器的传输系统 - Google Patents

使用可变长度编码器的传输系统 Download PDF

Info

Publication number
CN1237291A
CN1237291A CN98801285A CN98801285A CN1237291A CN 1237291 A CN1237291 A CN 1237291A CN 98801285 A CN98801285 A CN 98801285A CN 98801285 A CN98801285 A CN 98801285A CN 1237291 A CN1237291 A CN 1237291A
Authority
CN
China
Prior art keywords
symbol
variable length
sequence
length code
variable
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.)
Granted
Application number
CN98801285A
Other languages
English (en)
Other versions
CN1126270C (zh
Inventor
R·陶里
R·J·斯勒伊特
A·J·格里茨
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.)
Funai Electric Co Ltd
Original Assignee
Koninklijke Philips Electronics NV
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 Koninklijke Philips Electronics NV filed Critical Koninklijke Philips Electronics NV
Publication of CN1237291A publication Critical patent/CN1237291A/zh
Application granted granted Critical
Publication of CN1126270C publication Critical patent/CN1126270C/zh
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Images

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/40—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/40—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
    • H03M7/42—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code using table look-up for the coding or decoding process, e.g. using read-only memory

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)
  • Transmission Systems Not Characterized By The Medium Used For Transmission (AREA)

Abstract

在传输系统中利用可变长度编码器来减小符号序列的平均位速率。为了限制代码的最大长度,建议在编码符号的长度小于预定值时才以编码的形式发送符号序列。

Description

使用可变长度编码器的传输系统
本发明涉及包括具有用于把输入符号序列编码成为可变长度编码序列的可变长度编码器的发射装置的传输系统，所述发射装置还包括用于经由传输介质把所述可变长度编码序列发射给接收机的发射机，所述接收机包括用于把所述可变长度编码符号解码成为解码符号序列的可变长度解码器。
本发明还涉及发射机、接收机、可变长度编码器、可变长度解码器、可变长度编码方法、可变长度解码方法、用于执行所述方法的包括计算机程序的有形介质以及包括可变长度编码符号的信号。
从Robert G.Gallager所著“信息理论和可靠的通信”一书(ISBN471290483)第3章“离散源的编码”pp.38-70中知道开篇中所述的传输系统。
开篇中所述的传输系统用于发射具有不等的概率的符号序列。可以采用以下方法更有效地发射这种序列：把短的编码序列用于具有高的概率的输入序列，而把长的编码序列用于具有低的概率的输入序列。
可变长度代码的例子是众所周知的莫尔斯(Morse)代码和霍夫曼(Huffman)代码。一般说来，利用可变长度编码方法的结果是减少必须发射的用于传送特定的输入符号序列的符号的数目。但是，也有可能是以下的情况：传送特定的输入符号序列所需要的符号数目显著地大于未编码的信息。如果输入符号序列包括具有低的概率的符号，则可能发生这种情况。在这种情况下，例如，可能出现以下的实际问题：缓冲器溢出或者不可能把编码的信息插入仅仅具有有限的可用于该编码信息的空间的帧中。
本发明的目的是提供一种开篇中所述的传输系统，在该传输系统中不再出现上述问题，同时，不增加缓冲器的尺寸以及帧的尺寸。
为了实现所述目的，根据本发明的传输系统具有以下特征：如果若干可变长度的编码序列的组合长度超过预定的值，则安排所述发射装置把输入符号序列传送到所述发射机，所述可变长度的编码序列的数目大于或者等于1；以及如果若干可变长度的编码序列的组合长度超过预定的值，则安排所述接收机把接收到的未编码的符号序列传送到输出端。
通过确定可变长度编码序列的长度，以及通过在可变长度的编码序列的长度超过预定值时发射所述输入序列，就有可能把发射的符号序列的长度限制在输入序列的长度上。从而利用预定值来限制所发射的符号序列的长度。
有可能确定每一个单独的可变长度编码符号序列(例如，字)的长度以及确定该长度是否超过预定值。还有可能确定多个可变长度编码符号序列的组合长度以及确定该组合长度是否超过(大于)预定值。
本发明的实施例具有以下特征：所述预定值是所述各输入符号序列的组合长度。
通过使所述预定长度等于输入符号序列的长度或者等于多个输入符号的组合长度，就达到以下目的：限制所述符号序列的长度，并且所述发射机总是能够分别在可利用的缓冲器或者传输帧的可利用的空间中存储或者发射其信息。
本发明的另一个实施例具有以下特征：安排所述发射装置发射指示符，所述指示符表示至少发射一个输入符号序列，而不是发射相应的可变长度编码符号序列；以及安排所述接收机把接收到的未解码的符号序列传送到其输出端或者把接收到的符号序列传送到可变长度解码器的输入端。
通过在所传输的信号中引入指示符，对于接收机来说，确定必须执行什么操作(将接收到的符号序列解码或者将所述接收到的符号序列直接传送到输出端)就变得非常容易。
下面将参考附图说明本发明。附图中：
图1示出根据本发明的第一实施例的传输系统；
图2示出用于根据本发明的传输系统的编码器5的可供选择的实施例；
图3示出用于本发明中使用的霍夫曼解码器的霍夫曼解码树。
在根据图1的传输系统中，发射机2包括用于将各输入符号序列编码的编码器5。各输入符号序列包括具有预定长度的字，对于接着的字来说，预定的长度可能是不同的。把输入字加到编码器5的缓冲器8上。接着，把存储在缓冲器8中的字加到可变长度编码器上，后者在这里是霍夫曼编码器10。
可以用在霍夫曼编码器10的输出端提供对应于输入字的霍夫曼编码字的对照表来实现霍夫曼编码器10。所述表还在霍夫曼编码器10的输出端提供霍夫曼编码字的长度的指示。下面给出关于四位输入字的这种对照表的例子。
输入信号 霍夫曼代码 长度 输入信号 霍夫曼代码 长度
0000(0)     110110100  9  1000(8) 000  3
0001(1)     11011011  8  1001(9) 11010  5
0010(2)     110111  6  1010(10) 1101100  7
0011(3)     1100  4  1011(11) 1101101011 10
0100(4)     111  3  1100(12) 110110101011 12
0101(5)     10  2  1101(13) 110110101010 12
0110(6)     01  2  1110(14) 110110101000 12
0111(7)     001  3  1111(15) 110110101001 12
从上面显示的表可以清楚地看到，不同的霍夫曼编码的码字的长度显著地不同。根据可变长度编码方法的原理，把最短的霍夫曼代码赋予概率最高的输入字。在霍夫曼编码器10的输出端，把输入代码字和霍夫曼编码的字加到选择器12。还把霍夫曼编码器的输出信号中表示当前霍夫曼编码字的长度的那部分加到比较器上，后者把这种长度与预定的值进行比较。把比较器3的输出信号加到选择器12以及多路复用器14的输入端。如果霍夫曼编码序列比预定值大，则命令选择器12把霍夫曼编码器的输入字传送到其输入端。否则，把霍夫曼编码器的输出信号传送到选择器12的输出端。比较器3的输出信号作为“霍夫曼指示符”被包含在多路复用器14的输出信号中，用于使接收机能够确定是否必须将接收到的字解码。显然，可以用单一的表来实现霍夫曼编码器10、比较器3和选择器12的功能。下面给出这种表。
输入信号 输出代码 指示符 L 输入信号 输出代码 指示符 L
 0000(0)     0000  1  4  1000(8)     000  0  3
 0001(1)     0001  1  4  1001(9)     1001  1  4
 0010(2)     0010  1  4  1010(10)     1010  1  4
 0011(3)     0011  1  4  1011(11)     1011  1  4
 0100(4)     111  0  3  1100(12)     1100  1  4
 0101(5)     10  0  2  1101(13)     1101  1  4
 0110(6)     01  0  2  1110(14)     1110  1  4
 0111(7)     001  0  3  1111(15)     1111  1  4
为了通知多路复用器14要把多少位引入到其输出信号中，还把每一个字的长度存储在所述表中。可以看出，在所显示的实施例中使用一个表。但是，随后的输入字的特性(长度和概率)有可能显著地不同。在这种情况下需要使用关于随后的输入字的不同的编码表。
多路复用器14的输出信号被加到发射装置16，后者准备经由传输介质4把多路复用器14的输出信号发射到接收机6。发射装置16的任务包括信道编码和调制。
在接收机18中，接收装置18处理所述输入信号。由所述接收装置执行的操作包括放大、解调和信道解码。多路信号分解器20把所述“霍夫曼指示符”和选择器12的所述重构的输出信号分离。后者被加到霍夫曼解码器22的输入端以及选择器24的输入端。霍夫曼解码器22的输出信号被加到选择器24的另一个输入端。根据所述“霍夫曼指示符”的值，把多路信号分解器20的所述(未解码的)输出信号或者所述霍夫曼解码器的霍夫曼解码输出信号传送到选择器24的输出端。
图2的编码器5用来将多个霍夫曼编码字的长度之和与预定值进行比较。如果必须在帧的有限的空间尺寸中发射多个字，则这种比较会是有用的。通过将所述长度之和与可以是未编码字的长度之和的预定值进行比较，就有可能确定是完全以霍夫曼编码字的形式或者完全以未编码的字的形式发射所述多个字。
缓冲器30接收所述输入字并且把它们传送到缓冲器34的输入端以及霍夫曼编码器32的输入端。把霍夫曼编码器32的输出信号传送到长度计数器38以及缓冲器36。长度计数器38对在一定数目的编码码字范围内累加的霍夫曼编码码字的长度进行计数。例如，该数目可以是这样的码字数目，后者是必须在帧中发射的字的数目。
如果已经将所述多个字编码，则长度计数器38将所述累加长度与所述预定值比较并且确定要以霍夫曼编码的形式发射所述字或者要以未编码的形式发射所述字。这种决定被传送到选择器40以及多路复用器42。
根据长度计数器38的所述决定，选择器40在其输出端提供存储在缓冲器34中的一组完整的未编码字或者提供存储在缓冲器36中的一组完整的霍夫曼编码字。将选择器40的输出信号和长度计数器38的输出信号一起多路复用，以便获得编码器5的输出信号。长度计数器38的输出信号被作为“霍夫曼指示符”包含在所述输出信号中。
图3中示出上述霍夫曼代码的霍夫曼树。霍夫曼树包括一个起始节点A、多个中间节点B至P以及多个终结节点1至15。以其中存储着节点类型的数据结构的形式存储每一个节点。在中间节点的情况下，在存储指向后来的节点的指针的同时，还存储对应于从所述节点到所述接着的节点的过渡的位的值。在各终结节点中，存储对应的解码字的值。为了说明所述解码过程，霍夫曼编码字“1101100”对应于输入字“1010”(十进制的10)。在所述解码过程中，从左至右处理霍夫曼编码字。
在开始所述解码过程时，在节点A将所述过程初始化。接着，从所述编码字读出第一位(这里是“1”)。接着，检查哪一个接着的节点对应于当前位的值“1”。从存储在描述节点A的数据结构的信息中发现节点B是所述后续的节点。存储在描述节点A的数据结构中的指针用来寻找描述节点B的数据结构。
接着，利用存储在相应的数据结构中的信息检查节点B的类型。由于节点B是中间节点，所以，从所述编码字中读出下一位(这里等于“1”)。根据在描述节点B的数据结构中找到的信息发现对应于当前位的值“1”的接着的节点是节点D。
这样，从节点A经由节点B、D、F和G到节点H横过所述树。在节点H处确定：节点10是对应于末位值“0”的接着的节点。根据描述节点10的数据结构发现节点10是终结节点。因此，停止解码过程并且向所述输出端提供存储在对应于节点10的数据结构中的输出字“1010”。

Claims (9)

1．一种包括具有把输入符号序列编码成为可变长度编码序列的可变长度编码器的发射装置的传输系统，所述发射装置还包括用于经由传输介质把所述可变长度编码序列发射给接收机的发射机，所述接收机包括用于把所述可变长度编码符号解码成为解码符号序列的可变长度解码器，其特征在于：
如果若干可变长度编码序列的组合长度超过预定的值，则安排所述发射装置把所述输入符号序列传送到所述发射机，所述可变长度编码序列的数目大于或者等于1；以及
如果若干可变长度的编码序列的所述组合长度超过所述预定的值，则安排所述接收机把接收到的未编码的符号序列传送到输出端。
2．权利要求1的传输系统，其特征在于：所述预定值是所述各输入符号序列的组合长度。
3．权利要求1或者2的传输系统，其特征在于：
安排所述发射装置发射指示符，所述指示符表示至少发射一个输入符号序列，而不是发射相应的可变长度编码符号序列；以及
安排所述接收机把接收到的未解码的符号序列传送到其输出端或者把接收到的符号序列传送到所述可变长度解码器的输入端。
4．权利要求1、2或者3的传输系统，其特征在于：
所述可变长度编码器包括霍夫曼(Huffman)编码器；以及
所述可变长度解码器包括霍夫曼解码器。
5．一种具有用于把输入符号序列编码成为可变长度编码序列的可变长度编码器的发射装置，所述发射装置还包括用于经由传输介质发射所述可变长度编码序列的发射机，其特征在于：
如果若干可变长度的编码序列的组合长度超过预定的值，则安排所述发射装置把所述输入符号序列传送到所述发射机，所述可变长度编码序列的数目大于或者等于1。
6．一种包括用于把可变长度编码符号解码成为解码符号序列的可变长度解码器的接收机，其特征在于：根据所述接收到的符号序列的特性而安排所述接收机把接收到的未解码的符号序列传送到输出端。
7．一种包括将输入符号序列编码成为可变长度编码序列的编码方法，其特征在于该方法包括：如果若干可变长度编码序列的组合长度超过预定值，则把所述未编码的输入符号序列传送到输出端，所述可变长度编码序列的数目大于或者等于1。
8．一种包括将可变长度编码符号解码成为解码符号序列的解码方法，其特征在于该方法包括：根据所述接收到的符号序列的特性而传送接收到的未解码的符号序列。
9．一种包括可变长度编码符号的信号，其特征在于：所述信号包括表示所述符号是可变长度编码符号还是未编码的符号的指示符。
CN98801285A 1997-07-11 1998-06-18 使用可变长度编码器的传输系统 Expired - Fee Related CN1126270C (zh)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
EP97202165 1997-07-11
EP97202165.3 1997-07-11

Publications (2)

Publication Number Publication Date
CN1237291A true CN1237291A (zh) 1999-12-01
CN1126270C CN1126270C (zh) 2003-10-29

Family

ID=8228543

Family Applications (1)

Application Number Title Priority Date Filing Date
CN98801285A Expired - Fee Related CN1126270C (zh) 1997-07-11 1998-06-18 使用可变长度编码器的传输系统

Country Status (7)

Country Link
US (1) US6208274B1 (zh)
EP (1) EP0925651B1 (zh)
JP (1) JP3960629B2 (zh)
KR (1) KR100635794B1 (zh)
CN (1) CN1126270C (zh)
DE (1) DE69826971T2 (zh)
WO (1) WO1999003208A2 (zh)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1301013C (zh) * 2003-08-22 2007-02-14 阿尔卡特公司 传输用可变长码编码的图像或视频数据的方法及发射机

Families Citing this family (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7106794B2 (en) * 2000-08-11 2006-09-12 Broadcom Corporation System and method for Huffman shaping in a data communication system
US6690306B1 (en) * 2000-11-03 2004-02-10 Intel Corporation Method of generating a length-constrained huffman code
KR101389593B1 (ko) * 2001-08-23 2014-04-29 애플 인크. Ｃｏ-ｓｅｔ와 강하게 코딩된 ｃｏ-ｓｅｔ 식별자를조합하여 직교 진폭 변조를 행하기 위한 시스템 및 방법
DE60330198D1 (de) * 2002-09-04 2009-12-31 Microsoft Corp Entropische Kodierung mittels Anpassung des Kodierungsmodus zwischen Niveau- und Lauflängenniveau-Modus
EP1756950B1 (en) 2004-06-07 2009-04-29 Agency for Science, Technology and Research Systems and methods for scalably encoding and decoding data
US6987468B1 (en) * 2004-10-29 2006-01-17 Microsoft Corporation Lossless adaptive encoding and decoding of integer data
US8707139B2 (en) * 2006-10-18 2014-04-22 Kencast, Inc. Systems, methods, apparatus, and computer program products for providing forward error correction with low latency
US8179974B2 (en) * 2008-05-02 2012-05-15 Microsoft Corporation Multi-level representation of reordered transform coefficients
US8406307B2 (en) 2008-08-22 2013-03-26 Microsoft Corporation Entropy coding/decoding of hierarchically organized data
KR20120018360A (ko) * 2009-05-19 2012-03-02 노키아 코포레이션 가변 길이 코딩을 위한 방법 및 장치
CN103269257B (zh) * 2013-05-13 2016-08-24 杰发科技（合肥）有限公司 一种检测变长编码码流错误的方法和解码及错误检测装置

Family Cites Families (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US3185824A (en) * 1961-10-24 1965-05-25 Ibm Adaptive data compactor
US3394352A (en) * 1965-07-22 1968-07-23 Electronic Image Systems Corp Method of and apparatus for code communication
JPS61107818A (ja) * 1984-10-30 1986-05-26 Nec Corp エントロピ−符号化方式とその装置
JPS63181586A (ja) * 1987-01-23 1988-07-26 Nec Corp 可変長符号化回路
JPS63290021A (ja) * 1987-05-22 1988-11-28 Nec Corp 可変長符号化回路
JPS6412621A (en) * 1987-07-07 1989-01-17 Nec Corp Variable length decoding circuit
US5177480A (en) * 1988-12-07 1993-01-05 British Telecommunications Public Limited Company Data communication having transmitter-controlled mode switching from compressed-to-transparent mode but local synchronous transmitter-controlled and receiver-controlled mode switching from transparent-to-compressed mode
US4955066A (en) * 1989-10-13 1990-09-04 Microsoft Corporation Compressing and decompressing text files
US5220325A (en) * 1991-03-28 1993-06-15 At&T Bell Laboratories Hierarchical variable length decoder for digital video data
JP3474005B2 (ja) * 1994-10-13 2003-12-08 沖電気工業株式会社 動画像符号化方法及び動画像復号方法

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1301013C (zh) * 2003-08-22 2007-02-14 阿尔卡特公司 传输用可变长码编码的图像或视频数据的方法及发射机

Also Published As

Publication number Publication date
US6208274B1 (en) 2001-03-27
KR20000068519A (ko) 2000-11-25
WO1999003208A3 (en) 1999-04-01
DE69826971D1 (de) 2004-11-18
CN1126270C (zh) 2003-10-29
JP3960629B2 (ja) 2007-08-15
JP2001500350A (ja) 2001-01-09
EP0925651A2 (en) 1999-06-30
EP0925651B1 (en) 2004-10-13
DE69826971T2 (de) 2005-11-17
KR100635794B1 (ko) 2006-10-19
WO1999003208A2 (en) 1999-01-21

Similar Documents

Publication Publication Date Title
US5774081A (en) Approximated multi-symbol arithmetic coding method and apparatus
CN1237291A (zh) 使用可变长度编码器的传输系统
KR100318780B1 (ko) 데이터압축모드간스위칭방법및장치
KR920011266A (ko) 디지탈 송수신 방법 및 장치
EP1267581A3 (en) Moving picture coding and/or decoding systems
KR930020997A (ko) 디지탈 통신시스템용 가변길이 코드워드 디코드
KR960016576A (ko) 엔(n) 차원 트렐리스 부호 변조 방법, 신호 엔코딩 방법, 엔(n) 차원 트렐리스 부호 변조기, 신호 엔코딩 장치, 신호 송신 장치, 신호 처리 방법 및 신호 송신 방법
ATE269605T1 (de) Entropiekodierung von variabler zu variabler länge
JPS61212920A (ja) データ圧縮方法およびコード化された圧縮データの受信方法
SE454734B (sv) Forfarande och anordning for sendning och mottagning vid variabel lengdkodning
KR0124191B1 (ko) 가변길이 코드 디코딩장치
US5021782A (en) Variable length encoding method and variable length decoding method, encoding device and decoridng device for the implementation of this method
WO2002037690A2 (en) A method of generating huffman code length information
CN1115783C (zh) 高速可变长度码解码装置
EP0435802B1 (en) Method of decompressing compressed data
WO2005006562A1 (en) A method of decoding variable length prefix codes
US6049633A (en) Adaptive arithmetic codec method and apparatus
US6573847B1 (en) Multi-table mapping for huffman code decoding
US5864308A (en) System, coding section, arrangement, coding apparatus, and method
KR100636370B1 (ko) 결정 비트를 이용한 부호화 장치 및 그 방법과 그에 따른복호화 장치 및 그 방법
WO2005043765A2 (en) Resilient parameterized prefix codes for adaptive coding
EP3767469A1 (en) Data communication
KR20010058369A (ko) 코드길이에 따른 허프만 코드 복호장치 및 방법
KR100462060B1 (ko) 유니버셜 가변 길이 코드 부호어 다중 추출 방법 및 그를위한 룩-업 테이블 구성 방법
JPH0250667B2 (zh)

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
C14 Grant of patent or utility model
GR01 Patent grant
ASS Succession or assignment of patent right

Owner name: IPG ELECTRONICS 503 CO., LTD.

Free format text: FORMER OWNER: ROYAL PHILIPS ELECTRONICS CO., LTD.

Effective date: 20090828

C41 Transfer of patent application or patent right or utility model
TR01 Transfer of patent right

Effective date of registration: 20090828

Address after: British Channel Islands

Patentee after: Koninkl Philips Electronics NV

Address before: Holland Ian Deho Finn

Patentee before: Koninklike Philips Electronics N. V.

ASS Succession or assignment of patent right

Owner name: FUNAI ELECTRIC CO., LTD.

Free format text: FORMER OWNER: IPG ELECTRONICS 503 LIMITED

Effective date: 20120524

C41 Transfer of patent application or patent right or utility model
TR01 Transfer of patent right

Effective date of registration: 20120524

Address after: Osaka Japan

Patentee after: Funai Electric Co., Ltd.

Address before: British Channel Islands

Patentee before: Koninkl Philips Electronics NV

CF01 Termination of patent right due to non-payment of annual fee

Granted publication date: 20031029

Termination date: 20170618

CF01 Termination of patent right due to non-payment of annual fee