[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Rmt] Comments about RaptorG I-D and the uploaded RMT presentation

Title: Re: Comments about RaptorG I-D and the uploaded RMT presentation
Vincent,
Thanks for the support.  

On the specific questions about the complexity, the encoding and decoding is linear time for the Raptor described in RFC 5053 and for RaptorG.   I’d be happy to provide a presentation showing actual results, but it is too late to prepare this for the current RMT WG meeting.   I’d also be happy to explain why using “Gaussian elimination” does not mean that the running time is non-linear: Gaussian elimination is used in a smart limited way in both Raptor and RaptorG so that the overall complexity is linear (and fast linear). With respect to using GF(256) in RaptorG, again it is used in a very light way that maintains the very fast linear time encoding and decoding.  And, all of this is achieved for both Raptor 5053 and the new RaptorG using the decoding algorithms described in the specifications, which is the same independent of the source block size, i.e., there is nothing special we do for smaller versus larger block sizes in terms of how decoding works, and it is all spelled out in detail in the specifications.  I’d be happy to give a detailed lecture on that as well, but that would probably be more appropriate for a talk at a University.  (If you happen to be in San Diego next Monday, or at Palo Alto next Thursday, I will be giving lectures at UCSD and Stanford on exactly this subject! ).  

Sub-blocking is improved for a few reasons:
(1) Larger number of available source symbols means that sub-blocking can be more effective, as it allow longer source blocks to be used with limited receiver decoding memory.
(2) The derivation of the parameters for determining the number of source blocks and the number of sub-blocks is improved over that in RFC 5053.
(3) Because RaptorG has such strong recovery properties, one symbol per packet is recommended for even small file sizes.  This simplifies the derivation of the parameters, and allows the entire available packet size to be filled with the single symbol carried in each packet versus more than one symbol in a packet as sometimes is the case for RFC 5053.
Regards,
Mike
 


On 11/10/09 9:12 PM, "Vincent Roca" <vincent.roca at inrialpes.fr> wrote:

Mike,

The results presented in your slides are pretty impressive. Great work!
However, with my colleagues, we have several comments WRT the
slides uploaded on the IETF site:
http://www.ietf.org/proceedings/09nov/slides/rmt-0.ppt

Concerning your claim (slide 6):
------
RaptorG code properties
* Linear time encoding and decoding
*  Comparable to Raptor specified in RFC 5053
------
And that's all, no attempt to justify these claims! Our questions:

1) Of "linear complexity" does not mean it's fast. An algorithm can be
of linear complexity while being an order of magnitude slower
than another one which is in O(k^2). As k increases in the range of
interest, it's even possible that the second algorithm be always
significantly faster than the fist one.

So I'd prefer to see encoding/decoding time evaluations, compared
to a well known, widely available, codec. We've been using Luigi's
Reed-Solomon to that purpose to compare with our LDPC codec,
see for instance (slide 10 or the links provided in slide 11):
http://www.ietf.org/proceedings/75/slides/fecframe-5/fecframe-5.htm


2) RFC 5053 specifies that decoding can rely on a Gaussian elimination
technique, and explains how to do that. So the suggested decoding in
RFC 5053 is *by no means of linear complexity*.

draft-luby-rmt-bb-fec-raptorg-object-01 does exactly the same,
so the suggested decoding in the I-D is *by no means of linear
complexity*.

Admittedly, other decoding techniques can be used and what is in
the document is merely an example. However, at least with Raptor
(I don't know for RaptorG), an ML (Maximum Likelihood) type of
decoding remains required to achieve good erasure recovery
capabilities (iterative decoding is not sufficient with Raptor codes).

Can you clarify the kind of decoding algorithm used? Are you
considering your "inactivation decoding" technique, as described
in your Patent 6,856,263? Even in that case, it is not a purely
iterative decoder, and complexity is not, strictly speaking,
linear. In any case, it's a key point that must be clarified.


3) draft-luby-rmt-bb-fec-raptorg-object-01 considers source blocks
of size up to K'_max=56404. The same I-D suggests to use
Gaussian elimination for decoding. Is it realistic to suggest to
use a Gaussian elimination for such large source blocks? Do you
have practical recommendations?

I imagine a decoder will use different types of decoding
techniques, depending on the actual block size in use. Am I right?
At least this is the way our LDPC codec works...


4) Does RaptorG introduce additional complexity WRT Raptor? The
answer seems to be yes. From what I saw, RaptorG introduces
operations over GF(2^8) for the creation of some of the
Intermediate Symbols. It was not the case in Raptor where the
generator matrix for intermediate symbols was fully binary.
Having a matrix that is closer to a random matrix over GF(2^8)
is probably the key point to achieve the decoding performances
shown. However it makes math more complex. And it's the same
kind of math as that of Reed-Solomon codes over GF(2^8).

Can you clarify? What is your opinion, now you have developped
a Raptor codec? Do you have measurements that compare both
codecs (even if the codecs perhaps don't have the same maturity
level)?


5) You're saying that sub-blocking has been improved. I don't see
the fundamental differences but I probably missed something
here (I didn't check thoroughly). And what do you mean by
"improved derivation of parameters"?


The above comments should not be considered negatively. We
would just like to better understand some unclear points and
perhaps have them clarified in the I-D and/or future presentations.

That being said, *I do support this I-D to be WG Item*, of course.

Regards,

Vincent