发射器、接收器以及通信系统的制作方法

发射器、接收器以及通信系统
1.相关申请的交叉引用
2.本技术要求于2022年1月23日在美国专利商标局提交的美国临时专利申请第63/302,103号的优先权和权益，其全部公开内容通过引用并入本文。
技术领域
3.本公开的实施例的各方面涉及用于在通信链路中实现低开销转换编码的系统和方法。


背景技术：

4.在电子数据通信中，诸如在串行数据链路中，发送器与接收器之间的通信可以使用时钟恢复或时钟数据恢复(cdr)过程来同步。例如，接收器可以使用锁相环(pll)根据近似频率参考来生成时钟，并且然后使用cdr使生成的信号与数据流中的(高信号电平与低信号电平之间的)转换进行相位对齐。然而，如果数据游程长度(例如，连续的1或0的序列)由于没有足够数量的转换供接收器检测而超过特定长度，则时钟信号的恢复可能失败。


技术实现要素：

5.本公开的实施例的各方面涉及使用算术编码(诸如非对称数字系统)来执行分组编码和解码以控制出现在数据链路上的代码字。这种在出现在数据链路上的代码字施加的控制或约束可以用于例如限制游程长度和/或控制数据链路上的信号在高信号电平与低信号电平之间的平衡。
6.根据本公开的一个实施例，发射器包括：存储器，被配置为存储根据输入的数据分组的位序列计算的初始状态；以及算术解码器，被配置为基于输入位和符号频率表生成符号，其中，符号频率表将一个或多个排除的符号的频率设置为0并且将一个或多个允许的符号的频率设置为非零值，发射器被配置为将初始状态供应至算术解码器作为输入位，以迭代地生成受限分组的序列和结束状态，受限分组的序列排除一个或多个排除的符号的实例，并且发射器被配置为在信道上传输受限分组的序列和结束状态。
7.发射器可以进一步包括：分组缓冲器，被配置为以反转的序列存储输入的数据分组。
8.发射器可以进一步包括：伪随机数生成器，被配置为生成伪随机序列，其中，初始状态可以基于伪随机化数据分组来计算，该伪随机化数据分组根据输入的数据分组的位序列和伪随机序列来计算。
9.发射器可以进一步包括异或电路，该异或电路被配置为通过计算伪随机序列与输入的数据分组的位序列的异或来生成伪随机化数据分组。
10.发射器可以进一步被配置为更新符号频率表以将附加符号的频率设置为0。
11.发射器可以进一步被配置为更新符号频率表，以将一个或多个排除的符号的频率设置为非零值。
12.算术解码器可以是非对称数字系统(ans)解码器。
13.ans解码器可以是表ans解码器。
14.根据本公开的一个实施例，接收器包括：算术编码器，被配置为基于输入状态、输入符号和输出符号频率表计算状态，其中，符号频率表将一个或多个排除的符号的频率设置为0并且将一个或多个允许的符号的频率设置为非零值，接收器被配置为：将从信道接收的结束状态以及从信道接收的受限分组供应至算术编码器以迭代地生成最终状态，受限分组排除一个或多个排除的符号的实例；并且根据最终状态恢复位序列；以及存储器，被配置为存储基于恢复后的位序列计算的恢复后的数据分组。
15.接收器可以进一步包括：符号缓冲器，被配置为以反转的序列存储受限分组。
16.接收器可以进一步包括：伪随机数生成器，被配置为生成伪随机序列，其中，接收器可以被配置为基于伪随机序列和恢复后的位序列来计算恢复后的数据分组。
17.接收器可以进一步包括异或电路，该异或电路被配置为通过计算伪随机序列与恢复后的位序列的异或来生成恢复后的数据分组。
18.接收器可以进一步被配置为更新符号频率表，以将附加符号的频率设置为0。
19.接收器可以进一步被配置为更新符号频率表，以将一个或多个排除的符号的频率设置为非零值。
20.算术编码器可以是非对称数字系统(ans)编码器。
21.ans编码器可以是表ans编码器。
22.根据本公开的一个实施例，通信系统包括：发射器，该发射器包括：存储器，被配置为存储基于输入的数据分组的位序列计算的初始状态；和算术解码器，被配置为基于输入位和符号频率表生成输出符号，其中，符号频率表将一个或多个排除的符号的频率设置为0并且将一个或多个允许的符号的频率设置为非零值，发射器被配置为将初始状态供应至算术解码器作为输入位，以迭代地生成受限分组的序列和结束状态，受限分组的序列排除一个或多个排除的符号的实例，并且发射器被配置为在信道上传输受限分组的序列和结束状态；符号缓冲器，被配置为存储受限分组；以及接收器，该接收器包括：算术编码器，被配置为基于输入状态、输入符号和符号频率表计算输出状态，接收器被配置为将从信道接收的结束状态以及从信道接收的受限分组供应至算术编码器以迭代地生成最终状态，受限分组的序列排除一个或多个排除的符号的实例，并且接收器被配置为根据结束状态恢复位序列；和存储器，被配置为存储基于恢复后的位序列计算的恢复后的数据分组。
23.发射器可以进一步包括：发射器伪随机数生成器，被配置为基于种子值生成伪随机序列；和发射器异或电路，被配置为计算伪随机序列与输入的数据分组的位序列的异或，以计算伪随机化数据分组，其中，初始状态基于伪随机化数据分组计算，并且接收器可以进一步包括：接收器伪随机数生成器，被配置为基于种子值生成伪随机序列；和接收器异或电路，被配置为计算伪随机序列与恢复后的位序列的异或，以计算恢复后的数据分组。
24.发射器可以进一步包括：分组缓冲器，被配置为存储输入的数据分组的位序列；和符号缓冲器，并且接收器可以没有缓冲器。
25.接收器可以进一步包括：分组缓存器，被配置为存储恢复后的位序列；和符号缓冲器，并且发射器可以没有缓冲器。
26.算术解码器可以是非对称数字系统(ans)解码器，并且算术编码器可以是非对称
数字系统(ans)编码器。
27.通信系统可以进一步被配置为在算术解码器和算术编码器处更新符号频率表，以将附加符号的频率设置为0。
附图说明
28.附图与说明书一起阐释了本发明的示例实施例，并且与描述一起用于解释本发明的原理。
29.图1是发射器与接收器之间的串行链路的示意性框图，发射器包括根据本公开的实施例的编码器，并且接收器包括根据本公开的实施例的解码器。
30.图2是使用单极性线路码在数据链路上传输的二进制数据的描绘，其中逻辑1值被编码为逻辑电平高(h)信号并且逻辑0值被编码为逻辑电平低(l)信号。
31.图3是根据本公开的一个实施例的数据分组的示意性描绘。
32.图4是根据本公开的实施例的在六位字(q＝6)的示例场景中当数据被编码在数据分组中时的最大游程长度的示意性描绘。
33.图5描绘将m的范围划分成与代码的四个不同符号相对应的四个“时隙”或区域，其中，时隙基于符号的频率或计数而具有不同的尺寸。
34.图6是根据本公开的一个实施例的包括算术解码器的发射器的示意性描绘。
35.图7是描绘根据本公开的一个实施例的用于对原始数据进行编码以生成数据分组的方法的流程图。
36.图8是根据本公开的一个实施例的包括算术编码器的接收器的示意性描绘。
37.图9是描绘根据本公开的一个实施例的用于对编码数据进行解码以恢复原始数据的方法的流程图。
38.图10描绘了根据本公开的一个实施例的其中分组缓冲器位于接收器而不是发射器处的发射器和接收器对的实施例。
39.图11描绘了根据本公开的一个实施例的其中符号缓冲器位于发射器而不是接收器处的发射器和接收器对的实施例。
40.图12是根据本公开的一个实施例的针对6位代码字和含有两个排除的代码字的2048的总符号计数的情况示出每个符号的频率计数的图。
41.图13是根据本公开的一个实施例的针对6位代码字和含有四个排除的代码字的2048的总符号计数的情况示出每个符号的频率计数的图。
42.图14是根据本公开的一个实施例的针对10位代码字和8192的总符号计数的其中通过仅允许具有相等数量的0和1(汉明权重等于q/2)的代码字并且排除所有其他代码字而使代码字dc平衡的情况示出每个符号的频率计数的图。
具体实施方式
43.在以下详细描述中，通过图示的方式仅示出和描述了本发明的某些示例实施例。如本领域技术人员将认识到的，该发明可以以许多不同的形式体现并且不应被解释为限于本文所阐述的实施例。贯穿说明书，相同的附图标记指代相同的元件。
44.本发明的实施例的各方面涉及用于减小或最小化通信系统中的数字数据的游程
长度的系统和方法。更详细地，本公开的实施例的一些方面涉及用于对数字数据进行编码以保证受限的游程长度或保证数字数据的分组的游程长度小于或等于采用游程长度受限代码形式的特定限制的系统和方法。
45.图1是数据源1与数据宿2之间的串行链路的示意性框图，数据源1包括根据本公开的实施例的发射器100，并且数据宿2包括根据本公开的实施例的接收器200。在图1中示出的布置中，原始数据10从数据源1被传输到数据宿2，其中原始数据10由接收器200重构为解码数据18。解码数据18然后可以在数据宿2处由数据消费者20消费。更详细地，发射器100将原始数据10编码成编码数据30，并且编码数据30通过数据链路50被传输到接收器200。接收器200然后对编码数据30进行解码，以将其重构为解码数据18。
46.根据本公开的各种实施例，发射器100和接收器200可以分别被称为发射器电路和接收器电路，并且可以使用诸如一个或多个计算系统的中央处理单元(cpu)、应用处理器(ap)或应用处理单元(apu)、现场可编程门阵列(fpga)、专用集成电路(asic)、数字信号处理器(dsp)、显示驱动器集成电路(ddic)和/或图形处理单元(gpu)或其组合的各种处理电路来实现。例如，发射器100和接收器200可以是同一计算机系统的部件(例如，集成在单个外壳内，诸如在智能电话、平板计算机或膝上型计算机的情况下)，可以是计算机系统的分离的部件(例如，与外部监视器通信的台式计算机)，或可以是分离的计算机系统(例如，通过数据链路50通信的两个独立计算机系统)，或其变体(例如，在被配置为通过数据链路50进行通信的诸如微控制器的专用处理电路中实现的，其中微控制器是计算机系统内的外围设备)。如本领域技术人员将理解的，发射器电路可以使用与接收器电路的类型不同的类型的处理电路实现。另外，如本领域技术人员将理解的，各种处理电路可以是同一集成电路的部件(例如，作为同一个片上系统或soc的部件)，或者可以是可以通过印刷电路板上的引脚和线路连接的不同集成电路的部件。为了简明起见，发射器100和接收器200在文本中将各自被描述为包括处理器以及用于存储对处理器进行配置来执行各种操作的指令的存储器，其中，处理器和存储器在本文中将被解释为指采用其各种形式的处理电路，无论是特定操作是在软件(例如，通过执行指令的cpu或ap)中执行，在硬件中(例如，在配置的asic、fpga、gpu或ddic等的专用数字逻辑中)执行，还是在其组合(例如，利用在软件中执行的一些操作和在硬件中执行的其他操作)中执行。
47.作为具体示例，在用于控制显示装置的数据链路50的情况下，数据源1可以包括图形控制器，诸如计算机系统(例如，膝上型计算机、智能电话或平板计算机等)的生成图像数据作为原始数据的图形处理单元(gpu)或应用处理单元(apu)。该图像数据或原始数据10然后通过数据链路50被传输到显示面板(例如，液晶显示面板或有机发光二极管显示面板)，显示面板包括用于接收编码数据30并将编码数据30解码成解码数据18的接收器200。解码数据18然后可以被供应至数据消费者20，数据消费者20诸如是被配置为将接收的解码数据18转换成控制显示面板来显示如解码数据18中表示的图像(例如，图形用户界面、视频和其他显示元素)的信号的处理电路。
48.在数字通信中，发射器100和接收器200可以使用时钟恢复或时钟数据恢复(cdr)过程来同步。使用cdr过程的接收器通常通过检测数据链路的物理层上的符号(例如，链路上的信号的电压电平)之间的转换的时间并且基于检测到的转换来使接收器的时钟进行相位对齐而操作。
49.图2是使用单极性线路码在数据链路50上传输的二进制数据的描绘，其中逻辑1值被编码为逻辑电平高(h)信号并且逻辑0值被编码为逻辑电平低(l)信号。(本公开的实施例不限于与单极性线路码一起使用，并且还可适用于使用例如双极性线路码的数据链路)。逻辑电平高信号和逻辑电平低信号可以在数据链路上50分别物理地编码为高电压(例如，5伏特或3.3伏特)和低电压(例如，0伏特)。在图2中示出的示例中，正在通过数据链路50传输数据位序列101001110010。逻辑电平低(l)电压与逻辑电平高(h)电压之间的转换由箭头51示出。重复位的延伸(在此期间信号不改变)被称为游程。图2具体地突出了标记为52、53、54、55、56、57和58的七个不同游程及其对应的游程长度。基于数据位序列101001110010，游程52、53、54、55、56、57和58具有对应的游程长度1、1、1、2、3、2和1。
50.如果接收到的信号包含过长的游程长度(例如，具有相同电压电平的数据符号的长序列)，则cdr过程可能由于接收到的信号中没有足够数量的转换而失败，这可能在时钟的恢复中产生问题。例如，在单极性不归零(nrz)编码中，逻辑电平高值(例如，高电压)可用于编码1，并且逻辑电平低值(例如，低电压)可用于编码0。对任何特定输入数据的值进行直接编码可能导致任意长的游程长度。例如，全为零(0)的字的长序列或全为(1)的字的长序列将分别导致信号持续地处于逻辑电平低值或逻辑电平高值，而在位之间没有转换以用于cdr。虽然上面在单极性nrz编码的背景下描述了由长的游程长度引起的一些问题，但类似问题也可能存在于可以具有大于两个的信号振幅电平的其他类型的调制(例如，具有大于两个的电平的脉冲振幅调制或pam，诸如使用四个振幅电平的pam4)中。
51.因此，本公开的实施例的各方面涉及用于对输入数据进行编码以生成编码的数据位的系统和方法，其中编码的数据位被保证具有受限的游程长度(例如，不长于特定受限数量的位的游程长度)。以此方式限制编码的数据的游程长度改善了解码器执行cdr的能力，从而改善发送器与接收器之间的通信链路的质量。
52.本公开的实施例的一些方面涉及其中输入数据被编码成一个或多个数据分组的游程长度受限的代码，每个数据分组包括多个字。在以下描述中，每个数据分组包括k个字(或至多k个字)，并且其中，每个字具有q个位(换句话说，每个数据分组可以包括至多k个q位字)。因为每个字都具有q个位，所以每个字可以取q＝2q个可能的值(例如，当q＝6时，则q＝2q＝64，具有0到63的范围中的整数值)。图3是数据分组的示意性描绘。每个数据分组31因此可以被视作包括可以从0到qk-1被编号或索引(如在b[0:qk-1]中)的qk个位的有效载荷32。每个q位代码字w可以取从0到2
q-1的任意值，并且还可以表示为q位的数组，例如，b[0:q-1]。有效载荷32因此可能被视作一起被连接为qk个位的数组的k个字：
[0053]
w1,w2,
…
,wk[0054]
w1(b[0:q-1]),w2(b[q:2q-1]),
…
,wk(b[q(k-1):qk-1])
[0055]
为了便于说明，在以下示例中，q被设置为6，使得每个字的长度为6个位，具有0到63(6'b000000到6'b111111)的范围中的可能值。然而，本公开的实施例不限于此，并且根据编码和解码系统的设计参数和要求并且基于应用，q可以被设置为诸如8、10或16等的其他值。
[0056]
本公开的实施例的一些方面涉及通过确保编码数据30中没有一个字是全零(例如，q个连续的0)或全一(例如，q个连续的1)(诸如，在q＝6的情况下的6'b000000和6'b111111)，来确保编码数据的每个字中有至少一个转换。换句话说，本公开的实施例的一些
方面涉及从编码数据30消除全零和全一的字，或者确保编码数据30不包括(例如，没有)全零的字并且不包括任何全一的字。通过从编码数据中消除全零字和全一代码字，游程长度被限制为2(q-1)个位的最坏情况。
[0057]
图4是根据本公开的实施例的在六位字(q＝6)的示例场景中当数据被编码在数据分组中时的最大游程长度的示意性描绘。如图4中示出的，当6位字6'b100000(标识为字wi)后面跟着6位字6'b000001(标识为字w
i+1
)时，则有十个0(2
×
(6
–
1))的游程。相似地，当6位字6'b011111后面跟着6位字6'b111110时，则有十个1的游程。因为全零和全一字已被消除，所以任何其他成对的连续字会导致比2(q-1)个位的受限最大游程长度短的游程长度。
[0058]
另外，一些cdr系统在恢复以特定字提供时的时钟方面可能具有难度或较低的可靠性。例如，mueller-muller cdr系统可能具有0和1的交替模式的代码字(例如，在6位代码字的情况下，代码字6'b010101和6'b101010)的问题，并且往往无法恢复以这种代码字提供时的时钟。此外，可以保留一些代码字以用作在发射器100与接收器200之间作为带内信令的形式传输的命令，诸如保留的停止符号。
[0059]
相应地，本公开的实施例的各方面涉及用于从编码的消息中排除特定的、指定的代码字的通用技术。这种排除的代码字的示例包括但不限于全零(0)代码字(诸如6位6'b000000)、全一(1)代码字(诸如6位6'b111111)、交替值代码字(例如，6位代码字6'b010101和6'b101010)。
[0060]
因此，下面将关于用于对原始数据10进行编码以生成编码数据30的系统和方法更详细地描述本公开的实施例的各方面，其中编码数据30没有全为一或全为零的字(例如，没有一个字有q个0，并且没有一个字有q个1)。另外，本公开的实施例的各方面涉及用于对编码数据30进行解码以生成与原始数据10匹配的解码数据18的系统和方法，该解码数据18可以包括全为一的字和/或全为零的字。从编码排除特定代码字可以被认为是底数(base)或基数(radix)的改变。例如，6位代码字能够表示以64为底数的值，因为它可以取64个不同的可能值中的任何一个(以类似的方式，4位代码字能够表示十六进制值，其是16个不同的可能值中的一个)。排除全零值6'b000000和全一值6'b111111将代码字减少到底数为62的值。附加代码字也可以从编码中排除，诸如被保留以用作带内命令或者基于系统特性(例如，为了更好的cdr性能或改善直流dc平衡)的代码字。排除的代码字的数量可以表示为e。如上所述，对于q位代码字，有q＝2q个可能的代码字，所以编码数据的底数n是：
[0061]
n＝q-e
ꢀꢀꢀꢀ
(1)
[0062]
并且因此，执行底数的改变(或基数的改变)的这种编码系统的理论最佳效率为：
[0063][0064]
以更小的底数对相同数据进行编码通常导致附加的开销位，这决定了编码的实际效率。
[0065]
相应地，本公开的实施例的一些方面涉及将输入字编码为代码字的可配置编码器，其中编码器可重新配置为仅输出所有可能代码字的特定子集内的代码字(例如，其中直线编码器被配置为使得其不输出特定代码字或者其中特定代码字从输出中排除)。在一些实施例中，选择这些代码字排除以控制(限制)出现在传输线路或数据链路50上的编码数据的游程长度。在一些实施例中，代码字被排除为保留用于命令(例如，带内信令)的代码字，以省略代码字从而改善cdr性能，并且省略代码字从而导致dc平衡的数据分组(例如，相同
数量的0和1)。然而，本公开的实施例不限于此，并且根据各种实施例的编码器可以被配置为出于其他目的从编码消息中排除代码字。
[0066]
本公开的实施例的一些方面进一步涉及用于对编码数据位进行解码以恢复原始输入数据的系统和方法。
[0067]
本公开的一些实施例也易于实现，无论是在(例如，在诸如微控制器的处理器上运行的)软件中、在硬件(例如，数字逻辑)中还是在现场可编程门阵列(fpga)等中。例如，在一些实施例中，核心编码和解码过程仅执行移位、加法(和/或减法)和按位异或(xor)操作，而没有乘法或除法，并且可以在具有小的固定位宽的数据路径中实现。实施例的一些方面还涉及其中编码器和解码器可以被重新配置为在使用相同硬件时排除不同代码字的实现方式，从而允许在数据分组边界处切换编码(例如，编码器和解码器可以在使用相同的硬件实现方式的同时对不同数据分组应用具有不同的排除代码字的不同编码系统)。实施例的一些方面涉及发射器-接收器对，其中仅在单个位置中使用分组缓冲器(例如，仅在发射器100处的分组缓冲器，或者仅在接收器200处的分组缓冲器)，而不需要在发射器100和接收器200两者处的分组缓冲器。例如，在一些实施例中，在发射器100处不需要分组缓冲器。
[0068]
更详细地，本公开的实施例的一些方面涉及算术编解码器的使用，诸如非对称数字系统(ans)。更详细地，在一些实施例中，ans解码器用于生成编码数据的传输分组，并且ans编码器用于根据编码数据重新创建或恢复原始分组。
[0069]
通常，算术编码是熵编码的一种形式，其中更频繁出现的输入符号使用更少的位来表示(或编码)，并且不太频繁出现的输入符号使用更多的位来表示，导致总共使用更少的位。诸如霍夫曼编码的其他形式的熵编码将输入分离为部件符号(例如，在unicode文本的情况下为不同的unicode字符)并用代码替换每个符号。相反，算术编码将整个消息编码成单一数字。这具有允许每个符号部分位的效果，其能够更接近地匹配符号的熵。
[0070]
通常，给定从(例如，从0到n-1枚举的)可能的符号集合中取得的符号序列，算术编码器产生位(或字节)序列。给定位(或字节)序列，算术解码器产生符号序列，其中符号是从(例如，从0到n-1枚举的)可能的符号集合中取得的。如果符号s的频率计数是“平坦的”(例如，近似相等)，则算术编码器等效于基数转换或底数转换。非对称数字系统(ans)是一种算术编码器，其只需要一个值(状态)，并且在先进/后出的基础上进行操作。
[0071]
相应地，本公开的实施例的各方面涉及在发射器处使用诸如ans解码器的算术解码器，以将位序列(原始数据)映射到从符号的约束集合(例如，排除全零和全一符号以及任何其他排除的代码字)取得的符号的序列，以生成编码数据。类似地，本公开的一些方面涉及在接收器处使用诸如ans编码器的算术编码器，以将接收的符号的编码消息映射到原始数据的位序列。在发射器处使用的算术解码器和在接收器处使用的算术编码器使用符号频率表来配置，符号频率表指明在发射器与接收器之间的信道(例如，通信链路或数据链路)上发射的符号的序列中各种符号出现的频率。算术解码器和算术编码器被配置为通过在符号频率表中将那些排除的代码字或排除的符号的符号频率设置为零来排除特定代码字或符号。
[0072]
另外，如果原始符号的分布近似平坦，则不需要从发射器向接收器传输符号频率表，从而减少开销。
[0073]
在例如duda,jarek的“非对称数字系统：将霍夫曼编码的速度和算术编码的压缩
率结合的熵编码(asymmetric numeral systems:entropy coding combining speed of huffman coding with compression rate of arithmetic coding)”arxiv预印本arxiv:1311.2540(2013)以及duda,jarek等的“使用非对称数字系统作为霍夫曼编码的精确替换(the use of asymmetric numeral systems as an accurate replacement for huffman coding)”2015图像编码研讨会(pcs)ieee,2015中详细描述了非对称数字系统(ans)。其全部公开内容通过引用并入本文。为了完整起见，下面提供ans的基本介绍。
[0074]
如本文参考ans所使用的，变量s用于指示n符号集合中的符号，其可以从0到n-1进行枚举或排序。fs表示对应符号s的频率或计数。bs表示符号的累积频率，其中：
[0075]bs
＝b
s-1
+f
s-1
[0076]
ba＝0
[0077]
m＝bn[0078]
其中ba表示累积频率的初始值，并且m表示所有符号的总数。给定以上，从0到m的范围可以被认为被划分成n个不同的区域或“时隙”，每个不同的符号s都有一个时隙。每个时隙具有fs的尺寸，即，基于对应的符号s的频率或计数的尺寸，其中在0到m的范围内，更高频率的符号具有更大的时隙，并且更低频率的符号具有更小的时隙。有效的符号s必须具有大于零(例如，至少是1)的频率fs，以便由ans编码系统使用。当符号s的频率fs为0时，则该符号将不会出现在ans解码器的输出中(并且通常不能由ans编码器编码)。关于n个符号s中的每一个的计数或频率fs的信息可以由符号频率表来表示，该符号频率表从符号s映射到它们对应的频率fs。
[0079]
图5描绘将m的范围划分成与四个不同符号相对应的四个“时隙”或区域，其中，时隙基于符号的频率或计数而具有不同的尺寸。在此示例中，代码可以有四个符号s：“a”、“b”、“c”和“d”。为方便起见，这些符号可以映射到受限集合的非负整数(例如，0到b-1)，其中，在本例中为a
→
0、b
→
1、c
→
2和d
→
3。符号“a”可以具有计数fa＝5，符号“b”可以具有计数fb＝6，符号“c”可以具有计数fc＝3，并且符号“d”可以具有计数fd＝2。因此，假设符号的顺序是“a”、“b”、“c”、“d”：
[0080]
ba＝0
[0081]bb
＝ba+fa＝0+5＝5
[0082]bc
＝bb+fb＝5+6＝11
[0083]bd
＝bc+fc＝11+3＝14
[0084]bn
＝bd+fd＝14+2＝16
[0085]
因此，在该示例中，m＝bn＝16。
[0086]
给定要编码的符号序列中的下一符号s和当前状态x，在对ans的一些方法中，编码器根据以下公式应用编码函数c(s,x)来计算编码器的下一状态x
′
：
[0087][0088]
其中编码器被配置有符号频率表，并且编码器通过在符号频率表中识别对应的条目来查找与给定的符号s相对应的fs的值(累积频率bs也能够根据符号频率表计算和/或被预先计算并存储为符号频率表的一部分)。
[0089]
换句话说，下一状态x
′
基于如在符号频率表中指明的符号s的符号频率fs来对给定状态x和下一符号s进行编码。因此，可以通过以初始状态起始并且迭代地将当前状态与
序列中的下一符号进行组合以生成表示所有的编码符号的结束状态，来对符号序列进行编码。结束状态x的位表示与对符号序列进行编码的位序列的产生相对应。如上面公式(3)中所见的，随着每个附加符号s被编码，下一状态x
′
是比输入状态x大的值，这至少是因为输入状态x除以fs(向下舍入)并乘以m，并且因为m＞fs。因此，表示状态所需的位数量随着更多符号s被编码而增加。
[0090]
解码器对编码器所执行的操作进行反转，以恢复序列的符号。为了从当前状态x
′
计算序列的下一符号s，解码器找到满足以下关系的符号s：
[0091]bs
≤x
′ꢀ
mod m＜b
s+1
ꢀꢀꢀꢀ
(4)
[0092]
如之前，诸如bs和b
s+1
的累积频率值可以被预先计算并存储为用于配置解码器的符号频率表的一部分，或者可以根据符号频率fs计算。解码函数d(x
′
)根据以下公式基于识别的符号s计算下一解码器状态x：
[0093][0094]
换句话说，通过从当前状态x
′
提取下一符号s并且根据当前状态x
′
计算下一状态x并且不断迭代直到所有符号已被提取，来以先进/后出的方式从结束状态的接收的位表示提取符号。如上面公式(5)中所见的，随着每个附加符号s从输入状态x
′
被解码，下一解码器状态x的值小于输入状态x
′
的值，这至少是因为输入状态x
′
除以m(向下舍入)并且乘以fs，并且因为m＞fs。因此，表示当前状态所需的位数量随着更多符号s根据状态被解码而减少。
[0095]
除了描述状态x如何演变的以上描述和公式之外，还存在允许人们通过称为归一化的技术将状态x转换成流的附加观察。例如，对于表ans的情况，可以证明，只要状态x在m与2m-1之间，编码和解码就将是唯一的。流式传输位的一个示例方法是创建保持状态x的容器。随着状态x的值增长，在一些实施例中，编码器取出块的集合中的最低有效位(lsb)并且将这些lsb转移到输出流，因为那些lsb已知是固定的。然后状态x在m与2m-1之间重新归一化。因为通过频率表，每个符号的位的最大数量在ans中始终是已知的，所以块转移可以被推迟，直到容器几乎满了，这是因为容器尺寸是固定并且已知的。在一些实施例中，容器的典型尺寸是32个位或64个位，其中块尺寸为8个位，但是本公开的实施例不限于此，并且这些值可以基于实现方式而不同。在块内保持位顺序，使得编码器和解码器能够针对给定数量的位写入和读取相同的值。因为块尺寸是固定的，所以流传输的块顺序可以由编码器或解码器反转。对于高效的流传输，因为符号始终可以通过编码公式被转换到一状态，并且起始状态始终是任意的，所以利用第一个符号或位集合来设置起始状态。相反，解码器首先读取最先的log2(m)个位以确定解码器的起始状态(其为编码器的结束状态)。然后如本文所述的进行解码。当第二到最后的符号被解码时，剩余状态x描述首先被编码的符号。
[0096]
如上所述，解码器基于找到满足公式(4)中的不等式的符号—本质上是找到哪个“时隙”(例如，如图中5示出的)满足该关系，来计算符号s。此外，如上所述，bs＝b
s-1
+f
s-1
，并且因此“时隙”的尺寸基于符号s的频率或计数。因此，当执行编码时，与针对与更小的时隙相关联的符号(不太频繁出现的符号)相比，针对与大时隙相关联的符号(更频繁出现的符号)，需要更少的位来编码下一状态x
′
。如果符号s的频率或计数被设置为0，则解码器将不输出该符号s(例如，这是因为时隙的尺寸将为零)。
[0097]
本公开的实施例的各方面涉及使用通过将特定符号的频率或计数设置为零而配置的ans解码器或算术解码器，使得在执行要在通信信道上传输的数据分组的编码时不输
出特定符号(指定的位序列)。
[0098]
图6是根据本公开的一个实施例的包括算术解码器的发射器600的示意性描绘。在本公开的各种实施例中，图6中示出的各种块执行在硬件(例如，数字逻辑)中或在软件(例如，当由处理器执行时使处理器执行特定操作的程序指令)中实现的操作。如图6中示出的，包括要传输的位的序列(或位序列)的数据分组602作为输入被供应至发射器600，发射器600生成受限分组604，其中特定符号(例如，全1或全0的字)被限制或从可能的输出中排除。更详细地，在图6中示出的实施例中，算术解码器690用于将输入的位的序列转换成输出符号，其中可能的输出符号是代码字(例如，q位代码字，诸如继续上面示例的6位字)。在本公开的一些实施例中，算术解码器690在硬件(诸如在ap、gpu、ddic、dsp、fpga或asic等中实现的数字逻辑)中实现。在本公开的一些实施例中，算术解码器690诸如通过在包括算术逻辑单元(alu)的处理器(诸如cpu、ap或gpu)上执行指令而在软件中实现。
[0099]
如上所述，通过将特定代码字的频率或计数fs设置为零，算术解码器690将不输出那些特定代码字。如上所述，不希望传输的代码字的一些示例是全零代码字、全一代码字以及交替代码字(例如，在q＝6的情况下，则设置频率f6’
b000000
＝0，f6’
b111111
＝0，f6’
b101010
＝0和f6’
b010101
＝0)，算术解码器690将不输出这些特定字，从而确保游程长度不会超过2(q-1)个位(例如，在q＝6的情况下的10个位)，并且还通过mueller-muller cdr系统改善时钟的恢复。
[0100]
为了向算术解码器690提供表示数据分组602的适当的输入状态x，以生成要作为受限分组604传输的符号s(例如，每个符号是q位字)的序列，本公开的实施例的各方面涉及执行数据分组602的预处理。
[0101]
图7是描绘根据本公开的一个实施例的用于对原始数据进行编码以生成数据分组的方法700的流程图。
[0102]
在一些实施例中，编码器在操作710将数据分组反转(例如，将0x04fa7dee反转成0xee7dfa04)，使得由算术解码器690进行的字节的随后反转使数据以正确的顺序在数据信道中发射。(在一些可替代实施例中，从发射器600省略分组缓冲器610，并且相反可以在接收器处执行反转，如下面更详细地讨论的)。
[0103]
当应用算术解码器以生成编码符号并应用算术编码器以根据编码符号恢复数据分组时，当符号的分布均匀或尽可能接近均匀(或最大程度地平坦)时，算术解码器和算术编码器的效率是最高效的。然而，输入的数据分组602可能具有其中一些位序列可能比其他位序列出现的更普遍的任意数据，并且因此没有保证符号的实际分布或频率将是最大程度地平坦的。在其中输入序列不是最大程度的熵(例如，其中分布不均匀)的情形下，解码器可以使代码扩展(扩展输入数据，使得编码版本大于输入数据，从而降低代码的效率)。
[0104]
相应地，本公开的一些实施例包括固定的伪随机数生成器(prng)630。在操作730，利用固定的prng 630生成伪随机位的序列，如由种子值(例如，固定种子值，其中prng针对任何给定的种子值生成相同的伪随机位的序列)控制的。伪随机生成器的示例包括但不限于mersenne twister、xorshift生成器、well生成器、yarrow算法、流密码以及在输出反馈模式下运行的分组密码。异或(xor)电路650在操作750将数据分组的位与由固定的prng 630生成的位的伪随机序列组合，从而生成由于由固定的prng 630引起的随机化而几乎均匀的伪随机化数据分组，如下面更详细地讨论的。
[0105]
在一些实施例中，在其中输入的数据分组602具有足够均匀的数据分布(诸如其中输入的数据分组602是加密的数据或压缩的数据)的情形下，固定的prng 630和异或(xor)电路650被省略(连同省略该方法的对应操作730和750)，这是因为加密的或压缩的数据通常已经表现出均匀分布的特性。
[0106]
在操作770，发射器600以存储器670中的x个起始位作为提供至算术解码器690的初始状态。在各种实施例中，起始位的数量x可以基于与数据分组相关联的条件和要求进行调整。随着位的数量x增加，效率接近理论最大值。在一些实施例中，x小于状态的最大尺寸的位宽。算术解码器690然后重复地应用解码器函数d(x
′
)＝(x,s)以生成如上述的符号s的序列，其中算术解码器690被配置有符号频率表，该符号频率表针对特定的排除或限制的分组或代码字(例如，如上所讨论的，全零代码字、全一代码字、具有交替位值的代码字等)具有fs＝0。从解码器生成的符号的数量能够根据编码方案的效率和位的数量x(其是编码器和解码器先验已知的)来估计。在一些实施例中，根据效率将一个附加符号添加到总预测数量的符号以考虑预测中的一些不精确度。如果符号的实际数量小于预测，那么如果发射器600包括缓冲器，则附加随机值可能在最后被传输，其将不会被接收器读取，这是因为编码器通过输出位的数量先验地知道何时停止。在符号缓冲器在接收器处的一些实施例中，在符号分组恰好缺少预期总数的情况下，传输一些附加信息以识别序列的“头”。在一些实施例中，在被传输的消息的一个额外字中传输该附加信息，其中该字指示用于跳过“头”字的分组的数量(其是解码器的最终状态的最重要的受限分组)。下面将更详细地讨论关于算术解码器690的配置(以及关于图8描述的算术编码器830的配置)的细节。在一些实施例中，算术解码器690是非对称数字系统(ans)解码器。在一些实施例中，ans解码器是表ans(tans)编解码器，其仅需要表查找、移位和附加来基于输入状态(x)和符号(s)计算更新状态(x
′
)。包括tans编解码器的ans编解码器的实现方式在duda,jarek的“非对称数字系统：将霍夫曼编码的速度和算术编码的压缩率结合的熵编码(asymmetric numeral systems:entropy coding combining speed of huffman coding with compression rate of arithmetic coding)”arxiv预印本arxiv:1311.2540(2013)以及duda,jarek等的“使用非对称数字系统作为霍夫曼编码的精确替换(the use of asymmetric numeral systems as an accurate replacement for huffman coding)”2015图像编码研讨会(pcs)ieee,2015中被描述，其全部公开内容通过引用并入本文。
[0107]
在一些实施例中，在并行流中实现ans以换取时钟速度的门控(gates)。在一些实施例中，并行流如下实现：对于单流表ans(tans)系统，在根据状态确定编码所需的位数量之后，存在可以同时发生的两种操作：使用位的该数量来编码(1)根据旧状态获得的新状态；和(2)根据旧状态获得的位序列。在并行编码中，可以并行使用第二编码器和第二状态；回顾一下ans中的开始状态可以任意被选择。因此，通过将符号序列分成“偶数”符号和“奇数”符号，两个编码器以两种不同的状态并行操作(步骤1)并且并行创建位序列(步骤2)。然后将两个位流合并，诸如通过将在第一编码器中找到的位长度(其始终是第一步)发送至第二编码器，反之亦然。两个存储器位置不重叠，并且多端口存储器将允许该操作同时发生。类似地，对于单流ans解码器，第一步是确定要从输入位流中读取的位的数量。然后存在可以同时发生的两种操作：使用从输入位流读取的位的数量，解码器(1)根据旧状态计算新状态，和(2)从位流去除位。与ans编码器类似，ans解码器能够与具有不同状态的第一解码器
并行运行第二解码器和第二状态。两者之间的协调点是要从输入位流去除的位的数量。只要第二解码器知道位的数量，第一解码器就开始去除，反之亦然，然后可以并行地从输入位流去除这些位；等效地，可以更新指向数据流的指针。给定足够长的流来进行编码/解码，tans的并行特性能够扩展到与所要求的一样多的并行流。对于使用ans解码器的发射器600，结束状态(其必须被传输)通过在启动状态中编码的符号在位宽上进行平衡。所以，对于tans，具有多个编码器和等效解码器实际上没有压缩损失，除了为了获得最佳并行效率，符号的数量应该被编码器/解码器的数量整除。协调并行位流写入和读取能够导致o(log(x))损失，其中x是编码器/解码器的数量。正如并行实现方式中常见的那样，该通信损失能够被计算步骤“隐藏”会是可能的。
[0108]
发射器600传输算术解码器690的结束状态(例如，在输出最后的代码字之后的最后状态)，并且通过信道(例如，如图1中示出的数据链路50)向接收器传输受限分组或代码字。然而，结束状态必须作为受限底数(例如，不能包括排除的代码字的实例)中的代码字传输。因此，实施例的一些方面进一步涉及对结束状态进行编码以传输到接收器。在由算术解码器690在操作790执行的算术解码过程结束时，发射器600将解码器的结束状态转换为与起始值不同的新的基数(例如，将这些值转换为不同的底数，其中不同底数中的值被映射到对应的允许的代码字，并且不同底数中的任何值都不被映射到排除的代码字)。例如，在6位字(q＝6)并且m＝2
11
的情况下，则分组的11个位可以用作在操作770中识别的起始状态的x个位。解码之后的存储器内容能够总是作为两个6位受限字来发送。需要额外的位以便处理新基数中的溢出的情况(在该特定情况下，两个额外的位)，并且这些位按照被发送的字的数量被分摊。例如，对于从64排除两个6位字的情况，由于映射仅需要2048个值被映射到62
×
62＝3844个值，因此始终可以将11个位转换成两个6位受限字。
[0109]
图8是根据本公开的一个实施例的包括算术编码器830的接收器800的示意性描绘。图9是描绘根据本公开的一个实施例的用于对编码数据进行解码以恢复原始数据的方法900的流程图。
[0110]
如图8中示出的，接收器800从信道(例如，如图1中示出的数据链路50)接收受限分组和结束状态802，以重构最初供应至使用算术解码器生成受限分组和结束状态802的发射器的数据分组804。如上所述，在算术数字系统(ans)编码器/解码器中，在该状态中对符号进行编码和解码的过程使符号的顺序被反转(例如，在先进/后出(filo)基础或等效地后进/先出(lifo)基础上被处理)。因此，为了保持数据值的正确顺序，使符号顺序反转，使得最后的符号首先被编码器处理。这可以发生在发射器的输出端或接收器的输入端。更详细地，接收器800在操作910将接收的符号(例如，q位字)存储在符号缓冲器810中以使符号的顺序反转(参见例如描绘其中符号缓冲器位于发射器的输出端处的另一实施例的图11)，并且，在操作930，将受限分组(以反转的顺序)供应至以类似于如图6中示出的算术解码器690的方式配置的算术编码器830。在符号缓冲器在接收器中实现的事件中，可能需要用信号通知由解码器发射的确切字数，这是因为在使用ans时，基于效率和分组的尺寸，字的数量可能小于预测的字的数量。通常，将预测的值四舍五入以解决系统中的一些低效率问题。这样，编码器知道字中的哪一些是实际的起始字，并且可以跳过填充字(填充字可以是随机的受限分组或预定义的受限分组)。在符号缓冲器在发射器中实现的情况下(参见例如图11)，填充字可以在最后传输；它们将不被读取，这是因为编码器知道要输出的字节的最大数量。
在本公开的一些实施例中，算术解码器830在硬件(诸如在ap、gpu、ddic、dsp、fpga或asic等中实现的数字逻辑)中实现。在本公开的一些实施例中，算术编码器830诸如通过在包括算术逻辑单元(alu)的处理器(诸如cpu、ap或gpu)上执行指令而在软件中实现。
[0111]
如上所述，算术编码器830实现编码器函数c(s,x)＝x
′
，来基于先前状态x和下一符号s计算新状态x
′
。通过向算术编码器830供应接收的结束状态并且迭代地供应接收的受限分组作为序列的连续符号，算术编码器830恢复作为算术解码器690的输入(例如，从伪随机化数据分组中选择并且在图6的存储器670和图7的操作770存储的位)而供应的原始状态(上面关于图6和图7讨论的初始状态)，其中恢复的状态与自(伪随机化的)输入的数据分组中取出的x个位匹配。在一些实施例中，算术编码器830是非对称数字系统(ans)编码器。在一些实施例中，ans编码器是表ans(tans)编解码器，其仅需要表查找、移位和附加来基于输入符号(s)和输入状态(x)计算更新状态(x
′
)。在将消息的所有符号供应至算术编码器830以计算连续的状态之后，算术编码器830输出最终状态。用于数据分组的每组x个位的代码字的数量可以先验地设置(例如，并且根据需要进行填充，如上所讨论的)或者代码字的数量可以在边信道中发送。另一种低效率的方法包括发送指示代码字的序列的结束的停止符号。
[0112]
在操作950，存储器850存储由算术编码器830根据最终状态恢复的x个起始位，以输出伪随机化数据分组(假设数据没有损坏，在操作750计算的恢复的伪随机化数据分组)。
[0113]
在操作970，接收器800的固定的prng 870生成伪随机位序列。接收器800的固定的prng 870被配置有与发射器600的固定的prng 630的种子相同的种子，并且因此发射器固定的prng 630和接收器固定的prng 870两者生成相同的伪随机位序列。种子可以作为通过信道或通过边带在带内提供的边信息在发射器600与接收器800之间共享，或者可以是预共享的固定信息。例如，在预共享固定信息的情况下，发射器和接收器可以针对每个通信会话重新使用相同的种子，或者发射器和接收器两者可以基于共享的信息(例如，共享的固定值)和其他信息确定性地为它们各自的prng导出相同的新种子，以同步发射器和接收器(例如，代编号(epoch number)或时间戳)。
[0114]
在操作990，异或电路890计算伪随机化数据分组与伪随机位序列的异或(xor)，从而恢复原始数据分组。如上所述，尽管算术解码器/算术编码器由于先进/后出行为而具有反转符号的顺序的效果，但在操作710的数据分组的初始反转使异或电路890所输出的最终数据分组804具有与原始输入的数据分组602的位顺序相同的位顺序。
[0115]
对于自输入的数据分组中取出的x个位的连续序列重复上述过程，以在发射器处生成初始状态，直到整个数据分组使用如上述的ans解码器已被编码为受限分组和结束状态。相似地，受限分组的多个序列和对应的结束状态由接收器接收，并且使用如上述的ans编码器进行解码，以恢复数据分组的x个位的对应序列。另外，如上所讨论的，在一些实施例中，这些过程在发射器处跨多个ans解码器并且在接收器处跨多个ans编码器并行化。
[0116]
如上所述，图6、图7、图8和图9中示出的实施例阐释了这样的实施例：其中数据分组的反转发生在使用分组缓冲器610的发射器600处，并且其中接收器800包括符号缓冲器810以在算术编码器进行处理之前缓冲符号。然而，本公开的实施例不限于此。
[0117]
例如，图10描绘了发射器1060和接收器1080对的实施例，其中分组缓冲器1084位于接收器1080而不是发射器1060处，使得在接收器1080处执行数据的反转以恢复数据分组
中的数据的原始顺序。在这样的实施例中，所有的缓冲都在接收器1080处执行并且没有缓冲在发射器1060处执行(发射器1060没有缓冲器)。在图10中，附图标记1063、1065、1067和1069分别表示固定的prng、xor电路、存储器和算术解码器，并且附图标记1081、1083、1085、1087和1089分别表示符号缓冲器、算术编码器、存储器、固定的prng和xor电路。
[0118]
作为另一示例，图11描绘了发射器1160和接收器1180对的实施例，其中符号缓冲器1170位于发射器1160而不是接收器1180处。在这样的实施例中，所有的缓冲都在发射器1160处执行并且没有缓冲在接收器1180处执行(接收器1180没有缓冲器)。在图11中，附图标记1161、1163、1165、1167、1169和1170分别表示分组缓冲器、固定的prng、xor电路、存储器、算术解码器和符号缓冲器，并且附图标记1183、1185、1187和1189分别表示算术编码器、存储器、固定的prng和xor电路。
[0119]
如本领域技术人员将理解的，另一可能的布置将包括位于算术解码器与信道之间的发射器处的符号缓冲器以及在算术编码器与根据最终状态对x个起始位进行的恢复之间的在接收器的使数据的顺序反转的分组缓冲器。
[0120]
在哪里放置各种缓冲器的选择可以取决于工程权衡，诸如在接收器与发射器处包括存储器或用于缓冲数据的其他存储的相对成本。例如，在显示装置中，在发射器侧(例如，在图形适配器硬件中)包括存储器可能比在接收器侧(例如，在显示面板内)包括存储器更经济，在此情况下，在发射器中放置分组缓冲器和符号缓冲器两者可能比在接收器中包括分组缓冲器和/或符号缓冲器更加具有成本效益。
[0121]
如上所讨论的，发射器600的算术解码器690被配置为使得其不输出任何排除的符号(例如，使得输出被限于特定符号并且将排除的符号的实例排除)。对特定符号的这种排除允许为特定使用条件定制的线路码的设计，诸如限制线路码的游程长度(例如，通过排除全一和全零代码字)，排除与0和1的交替模式相对应的代码字(例如，在6位代码字的情况下，特定代码字6'b010101和6'b101010)，或通过确保每个代码字具有相等数量的0和1而允许直流(dc)平衡(例如，排除诸如6'b000100和6'b101101的代码字，并包括或允许诸如6'b001101和6'b000111的代码字)。
[0122]
通常，给定具有q个位的代码字尺寸的线路码，有q＝2q个可能的q位代码字，具有e个排除的代码字，使得有q-e＝n个允许的代码字。作为6位代码字(q＝6)的具体示例，有26＝64个可能的代码字，并且假定全零代码字(6’b000000)和全一代码字(6’b111111)是仅有的要排除的代码字，则e＝2，使得n＝64-2＝62。
[0123]
如上所述，在设计最高效率的算术代码时，希望线路码中的各种符号的频率(或分布)最大程度地平坦或最大程度地均匀，同时考虑与增加分布平坦度有关的其他权衡(诸如计算复杂度)。回顾一下，特定符号s的频率被表示为fs并且m是所有n个符号s的fs的总和，称为所有符号s的总计数。在这种情况下，任意特定符号s出现的频率fs近似为m/n。然而，如果m不能被n除尽(如果m mod n≠0)，则一些符号将比其他符号出现的频率高，使得符号的频率不是完全均匀或完全平坦的。选择m的更大值减小不同符号之间的频率差。然而，m的更大值需要更多的位来表示那些值(尤其是，m个位，其中m＝2m)，这从而增加发射器600的算数解码器690和接收器800的算数编码器830的复杂度。在非对称数字系统(ans)编码器/解码器的具体情况下，用于编码器和解码器的状态必须是唯一的，以具有一对一且映射的特性。当状态总是m与m2(x∈[m,m2))之间的值时，满足这些特性，这可以用log2m2位或2m个位来表
示。相应地，当使用具有2m个位的硬件位宽的硬件算术编码器或硬件算术解码器执行编码或解码时，状态可以被更新，其中具有较窄位宽的硬件编码器或解码器通常比具有较宽位宽的硬件编码器或解码器实现起来更便宜。
[0124]
继续以上示例，在q＝6并且e＝2以排除全零代码字(6'b000000)和全一代码字(6'b111111)的情况下，则n＝62。例如，选择m＝11使得m＝2
11
＝2048导致n＝62个符号中的60个具有33的频率，并且剩余的两个符号具有34的频率。m＝11的这种选择导致使用对具有2m＝22个位的位宽的状态执行算术的算术解码器和算术编码器。
[0125]
图12是根据本公开的一个实施例的针对6位代码字和含有两个排除的代码字的2048的总符号计数的情况示出每个符号的频率计数的图。如图12中示出的，将全零代码字(由等效十进制值0表示)和全一代码字(由等效十进制值63表示)的频率计数设置为零，使得代码字1至60具有33的频率计数并且代码字61和62具有34的频率计数。
[0126]
通常，频率计数可以根据以下公式计算：
[0127][0128]
f＝k-1
[0129]
a＝kn-m
[0130]
其中，a个符号将具有f的频率，并且其余的n-a个符号将具有f+1的频率。
[0131]
选择m的更大值将增加分布的均匀性，这是因为具有f的频率的a个符号与具有f+1的频率的n-a个符号之间的频率(或计数)的为1的计数的相对差被减少。然而，如上所述，增加m的权衡在于状态x的增加的位宽，它必须是m与m2(x∈[m,m2))之间的值，并且因此需要至少log2m2个位来表示状态x。
[0132]
图13是根据本公开的一个实施例的针对6位代码字和含有四个排除的代码字的2048的总符号计数的情况示出每个符号的频率计数的图。具体地，图13示出了通过将6'b010101(由等效十进制值21表示)和6'b101010(由等效十进制值42表示)的交替代码字以及全零代码字(由等效十进制值0表示)和全一代码字(由等效十进制值63表示)的频率设置为零使得算术解码器不输出这些代码字而将这些代码字排除的情况。返回参考以上注释，给定6位代码字，有q＝64个可能的代码字，其中的e＝4个代码字被排除。这留下了n＝q-e＝64-4＝60个允许的代码字或符号。再次考虑m＝11使得m＝2048的情况，有52个具有频率34的符号(在图13中示出为符号1到20、22到41以及43到54)和8个具有频率35的符号(在图13中示出为符号55到62)，其中符号0、21、42和63是e＝4个排除的符号。
[0133]
图14是根据本公开的一个实施例的针对10位代码字和8192的总符号计数的其中通过仅允许具有相等数量的0和1(汉明权重等于q/2)的代码字并且排除所有其他代码字而使代码字dc平衡的情况示出每个符号的频率计数的图。在一些情形下，通信系统可以要求直流平衡的字(例如，在通信链路或通道可能不稳定时的初始设置期间)。相应地，算术解码器和算术编码器可以被配置为排除所有的字，除了具有相等数量的0和1的那些。图14图示了其中q＝10(10位代码字)的一个示例。在这种情况下，有q＝2
10
＝1024个可能的代码字。那些1024个可能的代码字中只有252个代码字是dc平衡的(如可以通过检查帕斯卡三角形来确定的)，遗漏了可能代码字的大约76.4％。该代码的游程长度限制为10，其与使用6位代码字的排除了全零和全一代码字的代码的情况相同。该代码的效率是：
[0134][0135]
相比之下，在仅排除全零和全一字的6位代码字的情况下，效率为：
[0136][0137]
要求每个代码字都被直流平衡确保了任何给定的10位代码字都没有电压偏置。另外，假设信号幅度从-0.5到+0.5变化，20个位的最坏情况的不平衡是+/-0.25(50％)。相比之下，游程长度限制为10的没有dc平衡的编码系统的最坏情况是+/-0.42(83％)。
[0138]
本公开的实施例的一些方面涉及基于条件在排除不同代码字之间自适应地切换。当使用算术解码器和编码器生成代码字并且根据代码字恢复原始数据时，排除字完全由用于配置算术解码器和算术编码器的符号频率表驱动。
[0139]
例如，在发射器600与接收器800之间的通信链路的启动期间，除了全零和全一代码字(6'b000000和6'b111111)之外，还可能有必要排除交替代码字(例如，在6位代码字的情况下，6'b010101和6'b101010)，以确保嵌入式时钟的良好恢复。因此，可以使用与图13中示出的符号频率表相对应的符号频率表。排除四个代码字(e＝4)的这种编码系统具有大约98.44％的效率。
[0140]
当通信链路足够稳定时，可以放宽对交替代码字(例如，在6位代码字的情况下的6'b010101和6'b101010)的排除并且仅排除全零和全一代码字(6'b000000和6'b111111)。编码系统的这种改变通过简单地改变算术解码器690和算术编码器830使用的符号频率表(和分组长度)来实现，从而在使用相同的底层算法和硬件的同时将效率提高到99.23％。例如，在一些实施例中，通过更新符号频率表来进行改变，使得先前被设置为0的频率的一个或多个符号被设置为非零值(例如，等于或接近于具有非零频率的其他符号的值)。例如，修改符号频率表中的条目以将交替代码字(例如，在6位代码字的情况下的6'b010101和6'b101010)的符号频率fs设置为非零值同时保留全零和全一代码字(6'b000000和6'b111111)的符号频率的fs具有这样的效果：改变编码方案以允许交替代码字由发射器处的算术解码器输出，并且相似地允许接收器处的算术编码器能够接收交替代码字。
[0141]
作为另一示例，在一些实施例中，发射器或接收器整体地替换完整的符号频率表。
[0142]
在发射器和/或接收器处改变符号频率表的信息可以作为边信息(例如，带外)被传输。
[0143]
作为具有4位代码字和具有两个排除的代码字的实现方式的一个示例，最大游程长度为6，并且最大效率为log(14)/log(16)≈95.18％。在m＝128和14位的状态下，示例测量效率是31/33个分组(≈93.94％)。
[0144]
作为具有6位字和具有两个排除的代码字的实现方式的另一示例，最大游程长度为10，并且最大效率为log(62)/log(64)≈99.24％。在m＝512和18位的状态下，示例测量效率是126/127个分组(≈99.21％)。
[0145]
作为具有8位字和具有两个排除的代码字的实现方式的第三示例，在m＝32,768和30位的状态下，最大游程长度为14，并且最大效率为log(254)/log(256)≈99.86％。
[0146]
相应地，本公开的实施例的各方面涉及通过使用算术解码器来将输入数据解码成
符号流(其中从这些符号流中排除了特定符号(例如，特定q位代码字))并且使用算术编码器将符号流编码回成原始数据而实现近似最优分组编码代码的系统和方法。通过改变发射器处的算术解码器和接收器处的算术编码器所使用的符号频率表来实现解码器和编码器，算术解码器和算术编码器是可适配和可重新配置的。相应地，本公开的实施例的一些方面涉及自适应编码系统，其中通过在算术解码器和算术编码器处更新符号频率表来实现基于信道的条件和要求的代码改变，而不对用于实现发射器和接收器的方法或硬件进行其他改变。
[0147]
尽管上面在图形控制器与显示装置之间的串行链路的情景中描述了本公开的实施例的一个示例应用，但是本公开的实施例不限于此并且还可以应用于其他类型的串行数据链路以及用于连接到其他类型的外围设备和计算装置(诸如数据存储装置(例如，易失性或非易失性存储器和大容量存储装置等)、外部协处理装置(例如，外部图形处理单元和人工智能加速器等)、网络控制器、其他计算机系统、智能电话和其他便携式计算装置等)的串行数据总线中。
[0148]
本发明的实施例可以以本领域普通技术人员将理解的多种方式实现，并且本文使用的术语“处理器”可以指能够执行所描述的操作的任何计算装置，例如编程的通用处理器(利用存储在连接到该通用处理器的存储器中的指令编程)(例如，arm处理器)、现场可编程门阵列(fpga)和定制专用集成电路(asic)。本发明的实施例可以集成到串行通信控制器(例如，通用串行总线或usb控制器)、图形处理单元(gpu)、面板内接口以及被配置为发射和接收数字数据的其他硬件或软件系统中。
[0149]
尽管已经结合特定示例实施例描述了本发明，但应当理解，本发明不限于所公开的实施例，而相反，旨在涵盖包括在所附权利要求的精神和范围内的各种修改和等效布置。

技术特征：
1.一种发射器，包括：存储器，被配置为存储根据输入的数据分组的位序列计算的初始状态；以及算术解码器，被配置为基于输入位和符号频率表生成符号，其中，所述符号频率表将一个或多个排除的符号的频率设置为0并且将一个或多个允许的符号的频率设置为非零值，所述发射器被配置为将所述初始状态供应至所述算术解码器作为所述输入位，以迭代地生成受限分组的序列和结束状态，所述受限分组的序列排除所述一个或多个排除的符号的实例，并且所述发射器被配置为在信道上传输所述受限分组的序列和所述结束状态。2.根据权利要求1所述的发射器，进一步包括：分组缓冲器，被配置为以反转的序列存储所述输入的数据分组。3.根据权利要求1所述的发射器，进一步包括：伪随机数生成器，被配置为生成伪随机序列，其中，所述初始状态基于伪随机化数据分组来计算，所述伪随机化数据分组根据所述输入的数据分组的所述位序列和所述伪随机序列来计算。4.根据权利要求3所述的发射器，进一步包括异或电路，所述异或电路被配置为通过计算所述伪随机序列与所述输入的数据分组的所述位序列的异或来生成所述伪随机化数据分组。5.根据权利要求1所述的发射器，进一步被配置为更新所述符号频率表，以将附加符号的频率设置为0。6.根据权利要求1所述的发射器，进一步被配置为更新所述符号频率表，以将所述一个或多个排除的符号的所述频率设置为非零值。7.根据权利要求1至6中任一项所述的发射器，其中，所述算术解码器是非对称数字系统解码器。8.根据权利要求7所述的发射器，其中，所述非对称数字系统解码器是表非对称数字系统解码器。9.一种接收器，包括：算术编码器，被配置为基于输入状态、输入符号和符号频率表来计算输出状态，其中，所述符号频率表将一个或多个排除的符号的频率设置为0并且将一个或多个允许的符号的频率设置为非零值，所述接收器被配置为：将从信道接收的结束状态和从所述信道接收的多个受限分组供应至所述算术编码器以迭代地生成最终状态，所述受限分组排除所述一个或多个排除的符号的实例；并且根据所述最终状态恢复位序列；以及存储器，被配置为存储基于恢复后的位序列计算的恢复后的数据分组。10.根据权利要求9所述的接收器，进一步包括：符号缓冲器，被配置为以反转的序列存储所述受限分组。11.根据权利要求9所述的接收器，进一步包括：伪随机数生成器，被配置为生成伪随机序列，其中，所述接收器被配置为基于所述伪随机序列和所述恢复后的位序列来计算所述恢复后的数据分组。
12.根据权利要求11所述的接收器，进一步包括异或电路，所述异或电路被配置为通过计算所述伪随机序列与所述恢复后的位序列的异或来生成所述恢复后的数据分组。13.根据权利要求9所述的接收器，进一步被配置为更新所述符号频率表，以将附加符号的频率设置为0。14.根据权利要求9所述的接收器，进一步被配置为更新所述符号频率表，以将所述一个或多个排除的符号的所述频率设置为非零值。15.根据权利要求9至14中任一项所述的接收器，其中，所述算术编码器是非对称数字系统编码器。16.根据权利要求15所述的接收器，其中，所述非对称数字系统编码器是表非对称数字系统编码器。17.一种通信系统，包括：发射器，包括：第一存储器，被配置为存储基于输入的数据分组的位序列计算的初始状态；和算术解码器，被配置为基于输入位和符号频率表生成输出符号，其中，所述符号频率表将一个或多个排除的符号的频率设置为0并且将一个或多个允许的符号的频率设置为非零值，所述发射器被配置为将所述初始状态供应至所述算术解码器作为所述输入位，以迭代地生成受限分组的序列和结束状态，所述受限分组的序列排除所述一个或多个排除的符号的实例，并且所述发射器被配置为在信道上传输所述受限分组的序列和所述结束状态；符号缓冲器，被配置为存储所述受限分组；以及接收器，包括：算术编码器，被配置为基于输入状态、输入符号和所述符号频率表来计算输出状态，所述接收器被配置为将从所述信道接收的所述结束状态以及从所述信道接收的所述受限分组供应至所述算术编码器以迭代地生成最终状态，并且根据所述最终状态恢复所述位序列；和第二存储器，被配置为存储基于恢复后的位序列计算的恢复后的数据分组。18.根据权利要求17所述的通信系统，其中，所述发射器进一步包括：发射器伪随机数生成器，被配置为基于种子值生成伪随机序列；和发射器异或电路，被配置为计算所述伪随机序列与所述输入的数据分组的所述位序列的异或，以计算伪随机化数据分组，其中，所述初始状态基于所述伪随机化数据分组来计算，并且其中，所述接收器进一步包括：接收器伪随机数生成器，被配置为基于所述种子值生成所述伪随机序列；和接收器异或电路，被配置为计算所述伪随机序列与所述恢复后的位序列的异或，以计算所述恢复后的数据分组。19.根据权利要求17所述的通信系统，其中，所述发射器进一步包括：分组缓冲器，被配置为存储所述输入的数据分组的所述位序列；和所述符号缓冲器，并且其中，所述接收器没有缓冲器。20.根据权利要求17所述的通信系统，
其中，所述接收器进一步包括：分组缓冲器，被配置为存储所述恢复后的位序列；和所述符号缓冲器，并且其中，所述发射器没有缓冲器。21.根据权利要求17至20中任一项所述的通信系统，其中：所述算术解码器是非对称数字系统解码器，并且所述算术编码器是非对称数字系统编码器。22.根据权利要求17所述的通信系统，进一步被配置为在所述算术解码器和所述算术编码器处更新所述符号频率表，以将附加符号的频率设置为0。

技术总结
本申请公开一种发射器、接收器以及通信系统。该通信系统包括：发射器，包括：算术解码器，被配置为基于输入位和符号频率表生成输出符号，该符号频率表将排除的符号的频率设置为0并且将允许的符号的频率设置为非零值，发射器被配置为迭代地生成受限分组的序列和结束状态，受限分组的序列排除一个或多个排除的符号的实例，并且发射器被配置为在信道上传输受限分组的序列和结束状态；和接收器，包括：算术编码器，被配置为基于输入状态、输入符号和符号频率表来计算输出状态，接收器被配置为：将从信道接收的结束状态和从信道接收的受限分组供应至算术编码器以迭代地生成最终状态，并且根据最终状态恢复位序列。根据最终状态恢复位序列。根据最终状态恢复位序列。


技术研发人员：格雷戈里
受保护的技术使用者：三星显示有限公司
技术研发日：2023.01.18
技术公布日：2023/7/26