Published
Edited
Jan 28, 2020
function getEncodedBlock(data, rsdCDFArray) {
const seed = Math.random()
const rng = seedrandom(seed)
const dUniform = rng()
let d = 1
for(let i = 0; i < rsdCDFArray.length; i++) {
if(dUniform < rsdCDFArray[i]) {
d = i + 1
break
}
}
const len = data.length
const out = new data[0].constructor(data[0].length)
for(let i = 0; i < d; i++) {
let sourceBlockIdx = Math.floor(rng() * len)
const next = data[sourceBlockIdx]
xorInplace(out, next)
}
return { out, seed, len, d }
}
function decodeSingleBlock(encoded, alreadyDecoded, holdingArea) {
let { out, seed, len, d, blocksUsed } = encoded
const rng = seedrandom(seed)
rng() // rng is used to compute D in encoding so we need to move it forward 1 time
if(blocksUsed == undefined) {
blocksUsed = new Set()
for(let i = 0; i < d; i++) {
const blockIdx = Math.floor(rng() * len)
blocksUsed.add(blockIdx)
const parents = holdingArea[blockIdx]
if(parents === undefined) {
holdingArea[blockIdx] = new Set([encoded])
} else {
holdingArea[blockIdx].add(encoded)
}
}
encoded.blocksUsed = blocksUsed
}
const blocksUsedIdxes = [...blocksUsed]
for(const blockIdx of blocksUsedIdxes) {
// if we have already decoded one of the source blocks used to make this block,
// xor it with the encoded data we got & remove it from the list of blocks needed to
// construct this block
if(alreadyDecoded[blockIdx] != undefined) {
const decodedSourceBlock = alreadyDecoded[blockIdx]
xorInplace(out, decodedSourceBlock)
blocksUsed.delete(blockIdx)
holdingArea[blockIdx].delete(encoded)
}
}
if(blocksUsed.size == 1) {
const items = [...blocksUsed]
const decodedIdx = items[0]
alreadyDecoded[decodedIdx] = out.slice()
let blocksDecoded = 1
// propogate new info
for(const pending of holdingArea[decodedIdx]) {
blocksDecoded += decodeSingleBlock(pending, alreadyDecoded, holdingArea)
}
return blocksDecoded
}
return 0
}
{
const testBlocks = Array.from({length: 256}, i => new Uint8Array([i, i, i, i, i, i, i, i]))
let res = []
let tbl = `
The following table shows the overhead for values of c and delta for a message of 256 blocks.
c is a free parameter, delta is the bound on decoding failing after Z packets have been recieved.
In the table, overhead is the mean extra fraction of packets needed to decode.
| c\\delta | 0.9 | 0.5 | 0.1 |
| ---- | ---- | --- | --- |
`
for(let c of [0.5, 0.1, 0.03, 0.01]) {
let reses = []
for(let delta of [0.9, 0.5, 0.1]) {
let packetsSamples = []
let Z_p
for(let i = 0; i < 10; i++) {
const [cdf, Z] = rsdCDF(testBlocks.length, c, delta)
Z_p = Z
const firstBlock = getEncodedBlock(testBlocks, cdf)
let decoded = Array.from({length:firstBlock.len}, () => undefined)
let holdingArea = Array.from({length: firstBlock.len}, () => undefined)
let packets = 1
let remainingBlocks = firstBlock.len
remainingBlocks -= decodeSingleBlock(firstBlock, decoded, holdingArea)
while(remainingBlocks > 0) {
packets++
remainingBlocks -= decodeSingleBlock(getEncodedBlock(testBlocks, cdf), decoded, holdingArea)
}
for(let i = 0; i < 256; i++) {
for(let j = 0; j < testBlocks[i].length; j++) {
if(decoded[i][j] != testBlocks[i][j]) {
return 'error: decoded output doesn\'t match input'
}
}
}
packetsSamples.push(packets)
}
const overhead = (packetsSamples.reduce((x, y) => x + y, 0.0) / packetsSamples.length) / 256
reses.push(`Z:${Z_p.toFixed(3)}, overhead:${overhead.toFixed(3)}`)
}
tbl = tbl + `|${c}|` + reses.join('|') + '|\n'
res.push(reses)
}
return md`${tbl}`
}
seedrandom = require('seedrandom')
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
