3GPP喷泉码介绍

1、.喷泉码标准 3GPP MBMSRaptor是喷泉码的一种，即编码器能根据需要由源符号块将可能多的生成的编码符号，而解码器是能够从任何略多于源符号数的编码符号中将源符号解码出来。Raptor码前向纠错码可用于MBMS的文件传输和MBMS流媒体应用上。1.定义和符合1.1定义源块（Source block）: 是一个包含K个源符号的数据块.源符号（Source symbol）:用于编码的最小数据单元，任意一个源块中的源符号大小都是相同的。编码符号（Encoding symbol）: 编码符号包含在数据包中. 编码符号分为源符号和Repair 符号，由某个源块中的源符号产生的Repair符号的大小

2、和该源块中的源符号一样。 Repair symbol: 由源符号产生，而非源符号编码符号组（Encoding symbol group）: 由一组编码符号构成，这些编码符号一起被发送，并有相同的编码符号标识Encoding Symbol ID编码符号标识（Encoding Symbol ID）: 用于表示一个编码符号组中的编码符号和源符号的对应关系编码包（Encoding packet）: 携带编码符号的数据包子块（Sub-block）:一个源块可以分为数个子块。对一个包含K个源符号的源块来说，它的每一个子块由K个字符号构成，而每个源符号每个子块中的相应的子符号组成。子符号（Sub-symbo

3、l）: 一个符号的一部分，每个源符号每个子块中的相应的子符号组成。源包（Source packet）: 携带源符号的数据包Repair packet: 携带Repair符号的数据包1.2符号i, j, x, h, a, b, d, v, m代表正整数。ceil(x) 表示大于或者等于x的最小正整数，即向上取整choose(i,j) 表示在j个物品中不重复的取出i个物品的组合数floor(x) 表示小于或者等于x的最大正整数,即向下取整C 表示中间符号数组, C0, C1, C2, CL-1C 表示源符号数组, C0, C1, C2, CK-1 X 表示非负整数V0, V1 表示两数组，数组中元

4、素皆为4字节的整数, V00, V01, V0255 和V10, V11, V1255RandX, i, m表示伪随机数发生器Degv表示度发生器LTEncK, C ,(d, a, b)表示LT的编码符号发生器TripK, X 表示一个三元发生函2.数据文件2.1构造源块为了将Raptor编码应用在文件传输上，一个文件可以分为Z个数据块，这Z个源块能够由Raptor编码器独立编码。每一个源块有唯一的源块号(SBN)来区分，第一个源块的SBN为0，第二个源块的SBN为1，依此类推。每个源块由K个源符号组成，每个源符号的大小为T个字节，而每个源符号又由唯一的编码符号标识(ESI)来区分，第一个源符

5、号的ESI为0，第二个源符号的ESI为1，等等。每个源块可以划分为N个子块，而每个子块又由K个子符号构成，每个子符号的大小为T字节。注意到，对一个文件来说，其中的每个源块包含的源符号数即K值没有必要相同；对一个源块来说，其中的每个子块的子符号大小T也可不同。但是，一个文件中的每个源块的源符号大小T必须相同，同时，一个源块中的每个子块包含的子符号数K也必须相同。下图表示一个源块，其中每一个小框代表一个子符号大小为T字节，每一行表示一个子块，而每一列表示一个源符号。可以看出该源块由N个子块构成，该源块一个包含了K个源符号。在本例中，每个子块的子符号大小都是T字节（实际上可以不相同），这样每个源符号

6、的大小T=N* T。012K-1KK+1K+22K-12K2K+12K+23K-1(N-1)KNK-12.2源块和子块的分割源块和子块的分割需要知道如下参数：-F文件的大小，单位为字节-A符号标准参数, 单位为字节-T源符号大小，必须为A的倍数，单位为字节-Z源块数目-N每个源块中的子块数目这些参数的设置必须满足ceil(ceil(F/T)/Z) KMAX. 函数 Partition ：该函数的输入为一对整数(I, J) ，输出为四个整数 (IL, IS, JL, JS) ，其中 IL = ceil(I/J), IS = floor(I/J), JL = I IS J ，JS = J - JL

7、. 于是Kt = ceil(F/T)(KL, KS, ZL, ZS) = PartitionKt, Z (TL, TS, NL, NS) = PartitionT/A, N 这样，该文件就可以被分割为Z = ZL + ZS 个连续的源块, 前面的 ZL个源块，每个长度为KLT 字节后面的ZS 个源块，每个长度为KST 字节. 如果Kt T F ，那么最后一个源符号需要填充Kt T F 字节的零比特。.同时，每个源块可以被分为 N = NL + NS个连续的子块，前面的 NL 个子块每个包含K 个连续的大小为TL A 字节的子符号，后面的NS个子块每个包含K 个连续的大小为TS A 字节的子符号

8、。 2.3参数推导算法首先需要知道如下参数：-F文件大小，单位为字节-W子块的目标大小，单位为字节-P最大包负载大小，单位为字节-A符号标准参数, 单位为字节- KMAX 每个源块的源符号数目的最大值-KMIN 每个源块的源符号数目的最小目标值-GMAX 每个包的符号数目的最大目标值于是G = minceil(P KMIN/F), P/A, GMAX- 每个源块的源符号数目的估计值T = floor(P/(AG)AKt = ceil(F/T)- 文件的总符号数目Z = ceil(Kt /KMAX)N = minceil(ceil( Kt/Z)T/W ), T/A上面所求的 G 和 N 的值实际

9、上分别是它们的下界，实际操作上应略大于上述参考值。同时，上面的算法并不能保证T能够整除P，所以上面的P实际上也是个参考值。但是，如果选择的G值恰好能整除P/A，, 那么T则是 P 的约数，此时这个 P 值能够直接使用。我们给出W, A, KMIN 和GMAX 参考值如下W = 256 KBA = 4KMIN = 1024GMAX = 102.4举例W, A, KMIN 和GMAX 的值为上面给的参考值， P = 512。Table 2.4File size FGSymbol size TG*TKtSource blocks ZSub-blocks NKLKSTL ATS A100 KB6845

10、041,220111,2201,220N/AN/A100 KB8645121,600111,6001,600N/AN/A300 KB22565121,200121,2001,2001281281,000 KB15125122,000152,0002,0001041003,000 KB15125126,0001126,0006,000444010,000 KB151251220,0003146,6666,66740363.流媒体3.1参数推导算法首先需要知道如下参数：-B源块长度的最大值，单位为字节-P最大包负载大小，单位为字节-A符号标准参数, 单位为字节- KMAX 每个源块的源符号数目的最

11、大值-KMIN 每个源块的源符号数目的最小目标值-GMAX 每个包的符号数目的最大目标值上述参数必须满足ceil(B/P) KMAX.。于是G = minceil(PKMIN/B), P/A, GMAX- 每个包的符号数目的估计值T = floor(P/(AG)A上述T 值只是作为实际T 值的参考，实际使用的参数 T 应尽可能的整除P,或者当在利用全尺寸的Repair符号来恢复部分源符号时所取得T值要尽可能的降低浪费。 而且T值的选择也要考虑到源包大小的分布情况。我们给出W, A, KMIN 和GMAX 参考值如下A = 4KMIN = 1024GMAX = 103.2举例W, A, KMIN

12、 和GMAX 的值为上面给的参考值， P = 512Table 3.2Max source block size BGSymbol size TGT40 KB1048480160 KB4128512640 KB15125124.系统Raptor码编码 4.1编码概述C0, CK-1 表示K 个源符号， C0, CL-1 表示L个中间符号 。编码的第一步是由K个源符号产生L个中间符号，再使用LT编码将中间符号生成编码符号。4.2.编码第一步: 预编码4.2.1预编码关系X 满足X(X1) = 2K.的最小整数值S 满足 S ceil(0.01K) + X 的最小整数值H 满足 choose(H,

13、ceil(H/2) K + S的最小整数值H= ceil(H/2)L = K+S+HC0, CK-1 表示前面K个中间符号CK, CK+S-1 表示 S个 LDPC 符号, 初始化为零CK+S, CL-1 表示 H 个Half 符号, 初始化为零 这 S 个LDPC符号： CK, CK+S-1 ，通过下面的方法给出：For i = 0,K-1 doa = 1 + (floor(i/S) % (S-1) b = i % SCK + b = CK + b Cib = (b + a) % SCK + b = CK + b Cib = (b + a) % SCK + b = CK + b Ci该H 个

14、Half 符号通过下面方法来定义：gi = i (floor(i/2) i为任意的正整数，gi是Gray序列 gj,k 指第 j 个元素数,这里 j=0, 1, 2, , 该gi 有k 个非零比特位。于是, 该H 个Half 符号：CK+S, CL-1 通过下面方法定义：For h = 0,H-1 doFor j = 0,K+S-1 doIf bit h of gj,H is equal to 1 then Ch+K+S = Ch+K+S Cj.4.2.2中间符号定义Given the K source symbols C0, C1, CK-1 the L intermediate symbo

15、ls C0, C1, CL-1 are the uniquely defined symbol values that satisfy the following conditions: 1. The K source symbols C0, C1, CK-1 satisfy the K constraints Ci LTEncK, (C0, CL-1), (di, ai, bi), for all i, 0 i K.2. The L intermediate symbols C0, C1, CL-1 satisfy the pre-coding relationships defined i

16、n B.5.2.3.4.2.3如何计算中间编码C 表示数目为L的中间符号的列向量, C0, C1, CL-1.D denote the column vector consisting of S+H zero symbols followed by the K source symbols C0, C1, , CK-1A为LxL的矩阵：AC = D矩阵A 的计算方法如下：GLDPC 是S x K LDPC编码 符号产生矩阵，于是GLDPC (C0, , CK-1)T = (CK, , CK+S-1)TGHalf 是 H x (K+S) Half编码符号产生矩阵, 于是GHalf (C0, ,

17、CS+K-1)T = (CK+S, , CK+S+H-1)TIS 是S x S的单位矩阵IH 是H x H 的单位矩阵0SxH 是S x H 的零矩阵GLT是 KxL 的LT编码符号产生矩阵 所以,GLT (C0, , CL-1)T = (C0, C1, CK-1 )TKSHSGLDPCISZSxHHGHalfIHKGLTFigure B.5.2.5.2-1: The matrix A中间符号则为：:C = A-1D对任意的，是满秩矩阵，因而是可逆的。.4.3编码第二步: LT编码4.3.1随机数发生器随机数发生器RandX, i, m 通过定义如下：RandX, i, m = (V0(X +

18、 i) % 256 V1(floor(X/256)+ i) % 256) % m随机数发生器产生的数的值是一个介于0和m-1的整数。这里X是一个非负整数，m是一个正整数，V0, V1 表示两数组，数组中元素皆为4字节的整数, 即V00, V01, V0255 和V10, V11, V1255。4.3.2度发生器度发生器Degv 通过下面的方法定义, 这里v为非负整数，但小于 220 = 1048576.在Table B.5.4.2-1, 指数 j 满足 fj-1 v fjDegv = djTable B.5.4.2-1 Defines the degree distribution for encoding symbolsIndex