rjpfonseca
commented
6 years ago Hi Steve,
I will answer your questions right away, but in case you are in a hurry, you can check the code I adapted from yours in the bottom of this post.
First of all, to address your primary question, you should know that RaptorQ does not perform intra-symbol error correction on its own. What it does is perform symbol erasure correction, which means it can handle the absence of any symbol (source or repair), but any received symbol is assumed to be correct. RaptorQ is best used in a scenario where you can detect symbol errors in the received packets and discard those packets in case they're corrupted (e.g. by using a Message Authentication Code per packet or group of packets). If you need intra-symbol error correction and symbol erasure correction at the same time, then Reed-Solomon is a good example (although it is rate-fixed, unlike fountain codes like RaptorQ).
Regarding your other questions:
With a .6 loss value (and using OpenRQ.minRepairSymbols()), there are almost 8 Repair packets per each Source packet. Is this reasonable? I'm guessing that's an extreme setting that causes unusual outcomes
First note that in your code, you were passing an incorrect value for the number of source symbols. It should be obtained (per source block) from sbEnc.numberOfSourceSymbols() which returns approximately ceil(dataLen/symbSize) / numSrcBlks. So, in your example, the number of source symbols should be on average 2 per source block, and the average minimum number of repair symbols should be 6 (per source block).
Note that the number of repair symbols per source symbol should decrease as you increase the number of source symbols. For example, with a data length of 1600 bytes, a symbol size of 40 bytes and a symbol overhead of 1, then the average number of source symbols and minimum number of repair symbols (per source block) are 20 and 33, respectively.
Is there a decoder that automatically absorbs 'extra' Repair packets? I have to perform a hack to throw them away.
No, there isn't one that automatically does that, sorry. Also, there is a better way to do the packet receiving logic, which looks at the whole data as a whole to know when it is fully decoded, can accept packets from any source block in any order, and checks for decoding failure. Like so:
SourceBlockDecoder latestBlockDecoder;
Parsed<EncodingPacket> latestParse;
EncodingPacket pkt;
SourceBlockState decState;
int packNum = 0;
boolean abort = false;
while (bb.hasRemaining() && !decoder.isDataDecoded() && !abort)
{
latestParse = decoder.parsePacket(bb, false);
if (!latestParse.isValid())
{
abort = true;
}
else
{
pkt = latestParse.value();
latestBlockDecoder = decoder.sourceBlock(pkt.sourceBlockNumber());
decState = latestBlockDecoder.putEncodingPacket(pkt);
if (decState.equals(SourceBlockState.DECODING_FAILURE))
abort = true;
System.out.println("SB # " + pkt.sourceBlockNumber() + " packet#=" + packNum
+ " type=" + pkt.symbolType() + " state = " + decState );
}
packNum++;
}Hope this answers your questions satisfactorily.
Refactored code:
public void corruptByte()
{
int numSrcBlks = 2;
int dataLen = 16;
int symbSize = 4;
int symbolOverhead = 1;
double loss = .6;
fecParams = FECParameters.newParameters(dataLen, symbSize, numSrcBlks);
// Source is 77, 77, 77, ..
final byte[] data = new byte[fecParams.dataLengthAsInt()];
Arrays.fill(data, (byte) 77);
final ArrayDataEncoder enc = OpenRQ.newEncoder(data, fecParams);
ByteBuffer bb = ByteBuffer.allocate(5000); // something plenty big
for (SourceBlockEncoder sbEnc : enc.sourceBlockIterable())
{
for (EncodingPacket encodingPacketSource : sbEnc.sourcePacketsIterable())
{
encodingPacketSource.writeTo(bb);
}
/* THIS IS INCORRECT. NUM_SOURCE_SYMBOLS == sbEnc.numberOfSourceSymbols()
int numRepairSymbols = OpenRQ.minRepairSymbols(dataLen / numSrcBlks, symbolOverhead, loss);
*/
int numRepairSymbols = OpenRQ.minRepairSymbols(sbEnc.numberOfSourceSymbols(), symbolOverhead, loss);
if (numRepairSymbols > 0)
{
for (EncodingPacket encodingPacketRepair : sbEnc.repairPacketsIterable(numRepairSymbols))
{
encodingPacketRepair.writeTo(bb);
}
}
}
bb.flip();
// Corrupt first source byte
bb.put(8, (byte) 88);
/*
* Decode
*/
ArrayDataDecoder decoder = OpenRQ.newDecoder(fecParams, symbolOverhead);
SourceBlockDecoder latestBlockDecoder;
Parsed<EncodingPacket> latestParse;
EncodingPacket pkt;
SourceBlockState decState;
int packNum = 0;
boolean abort = false;
while (bb.hasRemaining() && !decoder.isDataDecoded() && !abort)
{
latestParse = decoder.parsePacket(bb, false);
if (!latestParse.isValid())
{
abort = true;
}
else
{
pkt = latestParse.value();
latestBlockDecoder = decoder.sourceBlock(pkt.sourceBlockNumber());
decState = latestBlockDecoder.putEncodingPacket(pkt);
if (decState.equals(SourceBlockState.DECODING_FAILURE))
abort = true;
System.out.println("SB # " + pkt.sourceBlockNumber() + " packet#=" + packNum
+ " type=" + pkt.symbolType() + " state = " + decState );
}
packNum++;
}
/*
* In order to throw away "extra" repair packets (e.g., after sourceBlockDecoder.isSourceBlockDecoded() == true),
* extra logic is needed to "peek" until we see next source block's first source packet
*/
/*
SourceBlockDecoder latestBlockDecoder;
Parsed<EncodingPacket> latestParse;
for (int sbn = 0; sbn < numSrcBlks; sbn++)
{
int packNum = 0;
boolean allBlockPacketsRead = false;
while (allBlockPacketsRead == false && latestParse.isValid() == true)
{
latestBlockDecoder.putEncodingPacket(latestParse.value());
System.out.println("SB # " + sbn + " packet#=" + packNum + " decoded = "
+ latestBlockDecoder.isSourceBlockDecoded() + " type=" + latestParse.value().symbolType());
packNum++;
latestParse = decoder.parsePacket(bb, false);
// Check if we've finished reading packets for this block
if (latestParse.isValid() == false || (latestBlockDecoder.isSourceBlockDecoded() == true
&& latestParse.value().symbolType() == SymbolType.SOURCE))
{
allBlockPacketsRead = true;
}
}
if (sbn < numSrcBlks - 1)
{
latestBlockDecoder = decoder.sourceBlock(sbn + 1);
}
}
*/
/* THIS IS NOT SUPPOSED TO WORK SINCE RAPTORQ ONLY FIXES SYMBOL ERASURES, NOT INTRA-SYMBOL ERRORS
byte[] dataArray = decoder.dataArray();
// The following fails - 88 is not "corrected"
assertArrayEquals(data, dataArray);
*/
}
nasamaher
jnorthrup
Hi,
First, thank you to all contributors of this impressive package - I appreciate the work put into this (and some of the JUnit tips I've picked up like Parameters =).
Second, apologies for hijacking an 'issue' for what may be my extreme ignorance but this seemed like the only place to contact devs/users. I'm an experienced developer but have very limited experience with error correction (some small Reed-Solomon experiments).
I must be doing something wrong because when I manually corrupt 1 (source data) byte in an encoded byte stream (that includes plenty of Repair packets), the corruption is not repaired after decoding. The (JUnit) method is below and uses a class similar to net.fec.openrq.DataIntegrityCheckTest.java. I have played with all the parameters at the beginning of the test to no avail.
Other questions:
Thanks for any insights!
Steve
=========================================
`