Design of Short-Length Message Fountain Code forErasure Channel Transmission

Zan-Kai Chong∗, Bok-Min Goi∗, Hiroyuki Ohsaki†, Cheng-Kuan Bryan Ng‡ and Hong-Tat Ewe∗∗Faculty of Engineering Science, Universiti Tunku Abdul Rahman, Kuala Lumpur, Malaysia.†Graduate School of Information Science and Technology, Osaka University, Osaka, Japan.

‡Unité de recherche, INRIA Sophia Antipolis, France.Email:{chongzk,goibm,eweht}@utar.edu.my∗, oosaki@ist.osaka-u.ac.jp†, cheng.kuan.ng@gmail.com‡

Abstract—The emergence of practical fountain codes (i.e. LT andRaptor codes) may be a presage of Internet evolution. However,the existing fountain codes are only efficient to a long-lengthmessage and it will not be useful to current Internet as themajority of which are short-length messages. This manuscriptdemonstrates the preliminary design of our short-length messagefountain code. Our proposed fountain code is simple in designand it is able to achieve a perfect decoding inefficiency ε = 0in an ideal channel and ε < 1 even in a channel of erasureprobability p = 0.5.

I. INTRODUCTION

In 1998, Byers et al. [2] introduced a novel idea of error-correction code where a message of finite length k canbe encoded into an infinite number of codewords and onemay recover the original message from any combination ofthe codewords of sufficient length, i.e. k (1 + ε) codewordsrequired to recover the original message and ε is the decodinginefficiency. Due to its capability in generating an infinitenumber of codewords, such a class of error-correction codeis given a name as fountain code (or rateless code).

In 2002, Luby [5] introduced the first practical fountain codenamed as Luby Transform (LT) code. The code selects themessage bits based on a well-designed degree distribution(named as Soliton distribution) such that messages can beencoded and decoded efficiently. Shokrollahi [7] further im-proved the decoding efficiency of LT code in his proposedRaptor code. The existence of fountain code may be a presageof Internet evolution, especially in the Transmission ControlProtocol (TCP). Many papers have discussed the impact offountain code in replacing the congestion avoidance algorithmin the network [6], [1], [4]. However, the current practicalfountain code (e.g. LT code and Raptor Code) are only efficientfor long-length message (typically, k > 10, 000) and it mayhave limited applications with the fact that majority of theInternet traffic is occupied by short-length messages instead.Therefore, a short-length message fountain code is needed forthe evolution to take place.

To pursue short-length message fountain code, Zhu et al. [8]proposed to adjust the degree distribution (Soliton distribution)of LT code dynamically during the encoding process. Theirmethod is able to achieve 99.5% complete decoding for amessage of length 2000. Li and Marland [3] studied different

type of short-length message rateless codes (a similar classto fountain code) in Additive White Gaussian Noise (AWGN)channel. However their findings are inappropriate to be appliedin the erasure channel (i.e. network transmission).

In summary, long-length message fountain code is well studiedin [5] and [7] and the development of short-length messagefountain code is just at the beginning stage. We perceive thata short-length fountain code should fulfil the followings:

1) Encode a message of finite length k into an infinitenumber of codewords and it is able to be decodedfrom k (1 + ε) codewords with the decoding inefficiencyε < 1.

2) Acceptable encoding and decoding complexity.

Our proposed short-length message fountain code uses asimple combination of xor-operator (multiplier), degree dis-tribution and two interleavers. Besides, the proposed fountaincode is able to achieve zero decoding inefficiency (ε = 0) inan ideal channel and ε < 1 for channel of erasure probabilityp ≤ 0.5.

In Section II, we discuss the encoding principle and thedesign of the encoder. Then numerical result on the completedecoding of the short-length message fountain code will bepresented in Section III. Lastly, the conclusion in Section IV.

II. PRELIMINARY DESIGN

This section describes the encoding principle as well as eachconstituent components of the encoder.

A. Principle of Encoding

Let a message of k bit length be represented as a sequencem1,m2, . . . ,mk. In each step, the encoder selects a certaincombination of the message bits and produces an output bit c.

Given that a list of output bits c1, c2, . . . (known bits), anunknown bit mi of an output bit ci can be solved if

1) mi is the only unknown bit of the output bit ci. Or,2) There exists an output bit cj (ci 6= cj) such that ci =

mi + cj , i.e. ci has an extra message bit than cj duringthe encoding process.

239

Figure 1: Constituent components of the encoder.

In other words, the codewords are decodable if each of thesubsequent codeword differs by only one message bit, e.g.

m1 +m2 + ...+mi−1 = ci−1, (1)

m1 +m2 + ...+mi−1 +mi = ci. (2)

Note that the expressions in 1 and 2 differ by only one messagebit, i.e. mi.

To realise the aforementioned method, we propose a degreedistribution of a degree length d and it will vary in betweend and d + 1 while shifting to right in each row (cf. Eq. 3).Each subsequent row differs from the previous by one bit andit circulates to the first bit when it arrives at the last bit.

D =

1 1 1 0 0 01 1 1 1 0 00 1 1 1 0 00 1 1 1 1 00 0 1 1 1 00 0 1 1 1 10 0 0 1 1 11 0 0 1 1 11 0 0 0 1 1...

......

......

...

. (3)

The degree distribution determines which message bits to beincluded in each encoding process. The oscillation of degreelength in between d and d + 1 will ensure the encoded bitsdecodable.

We will describe each constituent components of the encoderin Section II-B.

B. Design of Encoder

Generally, the encoder consists of four components - multi-plier, degree distribution and two interleavers. The two inter-leavers randomise the message bits and the output bit of themultiplier. The degree distribution decides which message bitsto be included in the encoding at each step such that they aredecodable at the receiver side. The multiplier performs thematrix multiplication for both interleaved message bits andthe row matrix from the degree distribution.

Given that a message of k length ~m = (m1,m2, . . . ,mk) befed into the encoder. Then, the interleaver π1 randomises themessage bits and it becomes

~x = π1 (~m)

= (x1, x2, . . . , xk) . (4)

The degree distribution will generate a row matrix of onesand zeros as discussed in Section II-A. Let ~d1 be the rowmatrix generated at cycle 1. The multiplier performs the matrixmultiplication for both ~x and ~d1 (or the transposed matrix(~d)T

) and an output bit is produced

y1 = ~x×(~d1

)T. (5)

Since we have k message length, the multiplier will continuefor k cycles and yield ~y = (y1, y2, . . . , yk). Then, ~y will befed into the second interleaver π2 and it produces k codewords

~c = π2 (~y)

= (c1, c2, . . . , ck) .

Let us denote the codewords produce in the first k cycle as~c(1) =

(c(1)1 , c

(1)2 , . . . , c

(1)k

)and it will be sent to the receiver

to decode. If the receiver receives insufficient codewords,another k cycles of encoding will be executed. The interleaverπ1 will randomise the message bits as ~x(2) and it feeds theminto the multiplier. The degree distribution will continue tosupply a series of row matrix for message bit selection andit produces output bits ~y(2). The second interleaver π2 willfurther randomise the output bits ~y(2) into ~c(2) and sends themto the receiver. The aforementioned process continues until thereceiver has received enough codewords to decode.

III. NUMERICAL RESULT

We use Python to construct a simulator that consists ofencoder, decoder and erasure channel. The encoder embodiesmultiplier, degree distributor and two interleavers as narratedin Section II. The decoder is a solver that runs a customisedmessage-passing algorithm.

We use the term packet and the codeword interchangeably inthe following text. Each packet generated by the encoder willbe fed into the erasure channel before reaching the decoder.In a channel of erasure probability p = 0.1, one packet willbe dropped for every 10 packets transmitted in the channel.The same mechanism applies to channel of erasure probabilityp = 0.3 and p = 0.5, where it drops 3 and 5 packets in every10 transmitted packets respectively. Each simulation scenariorequires the settings of message length, k and degree length,d and all the tests are repeated for 1000 times of randomseeds. Accordingly, we present the results as the probability ofcomplete decoding at various number of received codewords.

Figure 2 (a) presents the probability of complete decodingfor message length k = 30 and degree length d = 15. The

240

result indicates that the proposed fountain code is able toachieve a perfect complete decoding in an ideal channel, i.e.k (1 + ε) packets required for a complete decoding with thedecoding inefficiency ε = 0. Overall, an original message canbe decoded at less than 2k packets. Particularly, in a channelof erasure probability p = 0.1, the probability a message canbe decoded completely is as high as 70%, but at the expenseno more than 2 extra packets.

Increasing the degree length d = 20 while maintaining themessage length (k = 30), we demonstrate the simulationresult in Figure 2 (b). From observation, the proposed fountaincode has a bad decoding inefficiency in a channel of erasureprobability p = 0 and p = 0.1. However, it is able to achievea better decoding inefficiency when the erasure probability ishigher (ε < 1 at p = 0.5).

We theorise that the decoding inefficiency ε of the proposedfountain code depends on the degree length, d and the erasureprobability p of the channel. We further conjecture that theproposed fountain code is able to achieve a good performance(ε < 1 ) when the degree length is half of the message length,i.e. d = k

2 . Due to the space limit, we present one of thesupporting results in Figure 3, in which the result is presentedbased on the simulation settings k = 50 and d = k

2 = 25.

IV. CONCLUSION

This manuscript demonstrates the preliminary design of ourshort-length message fountain code. Besides the design sim-plicity, it is also able to achieve a perfect decoding inefficiencyε = 0 in an ideal channel and ε < 1 in a channel of erasureprobability p = 0.1 to p = 0.5.

REFERENCES

[1] Thomas Bonald, Mathieu Feuillet, and Alexandre Proutiére. Is the ”lawof the jungle” sustainable for the Internet? In INFOCOM, pages 28–36.IEEE, 2009.

[2] John W. Byers, Michael Luby, Michael Mitzenmacher, and AshutoshRege. A digital fountain approach to reliable distribution of bulk data.In SIGCOMM, pages 56–67, 1998.

[3] Haoming Li and I.D. Marsland. A comparison of rateless codes at shortblock lengths. IEEE International Conference on Communications (ICC),pages 4483–4488, 2008.

[4] Luis López, Antonio Fernández, and Vicent Cholvi. A game theoreticcomparison of TCP and digital fountain based protocols. ComputerNetworks, 51(12):3413–3426, 2007.

[5] M. Luby. LT codes. In The 43rd Annual IEEE Symposium on Foundationsof Computer Science, pages 271–280. IEEE, 2002.

[6] B. Raghavan and A.C. Snoeren. Decongestion control. In Proceedings ofthe Fifth Workshop on Hot Topics in Networks (HotNets-V), pages 61–66.Citeseer, 2006.

[7] A. Shokrollahi. Raptor codes. IEEE Transactions on Information Theory,52(6):2551–2567, 2006.

[8] H. Zhu, C. Zhang, and J. Lu. Designing of fountain codes with shortcode-length. In 3rd International Workshop on Signal Design and ItsApplications in Communications, pages 65–68. IEEE, 2007.

(a)

(b)

Figure 2: Total codewords required for a complete decodingof message of length k = 30: (a) degree length, d = 15, and(b) degree length, d = 20.

Figure 3: The proposed fountain code is able to achieve gooddecoding inefficiency (ε < 1) with message length k = 50 anddegree length d = 25.

241