30:T6fc,md`# Fountain Codes A simple implementation of the [Luby transform fountain code](https://en.wikipedia.org/wiki/Luby_transform_code). A fountain code is a way to encode a message into an infinite number of blocks, such that the reciever only needs to recieve a bit more than the length of message (in blocks) of _any_ of the encoded blocks to have a high probability of reconstructing the input data. How to use: ### Encoding: \`\`\` import { rsdCDF, getEncodedBlock } from '@aman-tiwari/fountain-codes' // Pad and split your data into equal sized blocks of Uint8Array type const data = [Uint8Array, Uint8Array, ...] // pick c and delta // you should tune based on your message size const c = 0.03 const delta = 0.9 // precompute the Robust Soliton Distribution CDF // Z * data.length is the expected number of blocks you'll need to encode // to successfully transmit all your data with probability 1.0 - delta const [cdf, Z] = rsdCDF(data.length, c, delta) // now you can encode blocks! yield getEncodedBlock(data, cdf) \`\`\` ### Decoding \`\`\` import { decodeSingleBlock } from '@aman-tiwari/fountain-codes' // get the first block const firstBlock = await recieveEncodedBlock() // initialise the working area const decoded = Array.from({length:firstBlock.len}, () => undefined) const holdingArea = Array.from({length:firstBlock.len}, () => undefined) let remainingBlocks = decoded.length remainingBlocks -= decodeSingleBlock(firstBlock, decoded, holdingArea) // loop until all blocks are decoded while(remainingBlocks > 0) { const encoded = await recieveEncodedBlock() remainingBlocks -= decodeSingleBlock(encoded, decoded, holdingArea) } // now decoded holds your result! \`\`\` Scroll further down to see the overheads for various values of \`c\` and \`delta\``31:T603,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 }32:T71f,{ 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}` }33:[] 2e:{"title":"Fountain Codes","cells":[{"id":0,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":97,"value":"function rsdCDF(K, c, delta) {\n const S = c * Math.log(K/delta) * Math.sqrt(K) \n\n const pivot = Math.floor(K/S)\n const robustCdf = []\n for(let i = 1; i < pivot; i++) robustCdf.push(S/K * 1/i)\n robustCdf.push(S/K * Math.log(S/delta))\n for(let i = pivot; i < K; i++) {\n robustCdf.push(0) \n }\n const idealCdf = [1.0/K]\n for(let i = 2; i < K + 1; i++) {\n idealCdf.push(1.0/(i*(i-1)))\n }\n\n let Z = 0\n for(const x of idealCdf) Z += x\n for(const x of robustCdf) Z += x\n \n const cdf = []\n for(let i = 0; i < K; i++) cdf.push((idealCdf[i] + robustCdf[i])/Z)\n let cumsum = 0\n for(let i = 0; i < cdf.length; i++) {\n cumsum += cdf[i]\n cdf[i] = cumsum\n }\n return [cdf, Z]\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":13,"value":"function xorInplace(x, y) {\n let len = x.length\n for(let i = 0; i < len; i++) {\n x[i] ^= y[i] \n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":12,"value":"function getEncodedBlock(data, rsdCDFArray) {\n const seed = Math.random()\n const rng = seedrandom(seed)\n const dUniform = rng()\n let d = 1\n for(let i = 0; i < rsdCDFArray.length; i++) {\n if(dUniform < rsdCDFArray[i]) {\n d = i + 1\n break\n }\n }\n const len = data.length\n const out = new data[0].constructor(data[0].length)\n for(let i = 0; i < d; i++) {\n let sourceBlockIdx = Math.floor(rng() * len)\n const next = data[sourceBlockIdx]\n xorInplace(out, next)\n }\n return { out, seed, len, d }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":39,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":47,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":4,"value":"seedrandom = require('seedrandom')","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}