[matroska-devel] EDC/ECC

thana thanatos666 at gmx.net
Tue Feb 18 16:53:24 CET 2003


hi again..

i had some time to think about EDC/ECC Elements, so i've read through the
old mcf-mailing lists and the mplayer-devel mailing list and did some
research on the web.. as far as i've seen there is only EDC defined yet,
using the crc-32 algorithm. someone has mentioned the use of crc-32 for ECC
too, but i think it's not very good for that purpose and isn't used anywhere
i can think of.

so far the best FEC (forward error correction) algorithm still seems to be
the Reed-Solomon code that is used on CD for EDC and ECC (CIRC - Cross
Interleaved Reed-Solomon Code) and also on DVD (RSPC - Reed Solomon Product
Code). one advantage of RS is that it is quite good at correcting
burst-errors, and i think that's most important for our uses since single
bit errors will probably get corrected by the the lower EDC-Layers of the
CD/HDD respectively the TCP-layers on networks. (UDP is another story, but
in that case FEC could be implemented on the streaming server as an
additional layer, or the server uses only matroska files that are already
ECC-ified, and then the client has to do error checking on the fly, or.. -
i'm going off-topic :)). for the purpose of downloading the file over a p2p
network EDC-checking should be enough, so that corrupted parts gets
redownloaded, which requires support of the p2p-program - but i think this
has already been mentioned some times here.

a good thing of RS-code is the ability to scale quite well.. you can use any
arbitrary amount of parity bytes.. f.e. a 255/223 RS-code (255 bytes total /
223 bytes data / 32 bytes Parity) will give us exactly 100MB overhead on a
700MB file.. 255/251 will give only 12,5 MB overhead.. so 1 byte parity
overhead equates to 2,73-3,12MB, which should be good enough regarding
granularity to fill an XCD..

I have already found some free code (GPL) for en/decoding of RS in C.. there
is also a C++ version, but that is not optimized for speed.. and yes, speed
IS a concern in this regard, from what i've learned, encoding should be
quite fast, but decoding is highly complex and speeds could be as low as
1MB/s on a 1GHz machine for a 255/223 RS-code.. also the speed depends on
the amount of parity bytes, a 255/251 RS-code is roughly 10 times faster as
255/223.. also, because of those speed restrictions, i think EDC-elements
should be preserved in the file even when ECC-elements exist..

regarding the placing of the ECC-elements in a matroska-file: should we put
them after every block, every cluster or every n clusters (f.e. after every
complete GOP-sequence, before the next keyframe)? or any of them depending
on the size of the blocks/clusters? are there upper/lower limits on how big
a block/cluster element can be? as i think an ECC-element for less data than
223 bytes would be quite inefficient..

i had some more questions about reindexing and reordering of matroska-files,
but i will come to those later, when i have more time to think about those..

thana




http://www.matroska.org



More information about the Matroska-devel mailing list