卢比变换码

在传统'抹去通道'（erasure channel）上的传输，通常得仰赖发送端以及接收端持续性的双向沟通：

• 发送端（sender）进行编码（encode）以及传送带有讯息（message）的封包（packet）。
• 接收端（receiver）这边在收到每个封包时会对其进行评估，如果该封包可以被解码（decode），则传送一个确认（acknowledgment）给发送端；反之，丢弃毁坏的封包，并传送请求让发送端再次发送该封包。
• 该双向沟通会持讯进行值到所有讯息的封包都被成功传送且解码为止。

然而，在现今网络上，出现许多如多点传输（multicast）的情形，此时发送端不可能持续性地跟所有接收端一一确认封包传递与否，然而为维持传输的正确性，必须使用涌泉码（fountain codes），特别是卢比变换码（LT码）这类型的方式传输：

• 发送端同样进行编码（encode）以及传送带有讯息（message）的封包（packet）。
• 接收端对每个收到的封包进行评估，如果出现错误，则丢弃该封包；反之则收纳作为讯息的一部分。
• 当接收端逐一收取封包直到拥有足够且可以完整解码（decode）的有效讯息时，才发送确认给发送端，停止传送封包。

将待传送的讯息分割成等长度的${\displaystyle n}$ 个封包（packet），

• 透过随机数产生器（random number generator）依特定的几率分布（probability distribution）产生一个整数degree d，且${\displaystyle 1\ll d\ll n}$ ，代表着一组讯息需要包含的封包数量。
• 接着在${\displaystyle n}$ 组封包中，以离散型均匀分布（uniform distribution）的方式，选取d组封包出来。
• 接下来将d组封包之间做异或（XOR）运算，因此要传送的其中一个封包便是：

　　${\displaystyle M_{1}\oplus M_{2}\oplus ...\oplus M_{d}}$ 

　　　　其中${\displaystyle M_{1},M_{2}...M_{d}}$ 是总共n组封包中被挑选出来的d组

• 该传送的封包前面还须附加一些额外讯息，包括整份讯息有多少个封包（n个）、是哪d个封包被做了XOR运算
• 最后，一些形式的侦错码将被附加在封包的最后（可能是某种循环冗余校验（cyclic redundancy check）），该封包才会被进行传输。

以上这些步骤将不断重复进行，直到接收端判断该讯息已被完整接收且成功地解码出来。

解码过程中同样使用"异或"（XOR, ${\displaystyle \oplus }$ ）来还原被编码的讯息。

• 如果当前这个封包格式错误（侦错码发生问题），或者该封包是个已处理过封包的复制品，丢弃该封包。
• 排除以上情形，便可开始处理解码程序；其工作原理是利用${\displaystyle A\oplus A=0}$ 的特性去逐步消去每个封包（packet）里的degree，直到总共有n个degree为1的不同packet为止。范例如下：

　　　　${\displaystyle (M_{1}\oplus ...\oplus M_{d})\oplus (M_{1}\oplus ...\oplus M_{k-1}\oplus M_{k+1}\oplus ...\oplus M_{d})}$ 

　　${\displaystyle =M_{1}\oplus M_{1}\oplus ...\oplus M_{k-1}\oplus M_{k-1}\oplus M_{k}\oplus M_{k+1}\oplus M_{k+1}\oplus ...\oplus M_{d}\oplus M_{d}}$ 

　　${\displaystyle =0\oplus ...\oplus 0\oplus M_{k}\oplus 0\oplus ...\oplus 0}$ 

　　${\displaystyle =M_{k}}$ 

^ M.Luby, "LT Codes", The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. （页面存档备份，存于互联网档案馆）