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

[Vincent Roca <[e-mail]>]

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