应用于对各类码进行编码和解码的原地变换

摘要

在使用具有存储器限制的计算设备编码数据码元的编码器中，一种执行变换的方法包括：将源块加载到该计算设备的存储器中；执行小于该源块的全部的中间变换，然后在存储器中用中间结果替换该源块的一部分并随后以存储在存储器中的输出码元构成经编码码元的集合的方式完成该变换。一种解码器以允许基本使用同一存储器来存储接收到的数据和已解码的源块的顺序执行解码步骤，从而就像执行原地(in-place)变换一样。使用原地变换，随着接收到的数据被变换为经解码的源数据，为接收到的数据所预留的大部分存储器可被重写而不需要类似大小存储器来用于经解码的源数据。

主权项

一种在将安排为多个源码元的数据编码为多个经编码的码元的编码器中执行从所述源码元到所述经编码的码元的变换的方法，其中所述源码元中的一定数目即k个将通过对于纠错码的生成矩阵B运算被变换为n个经编码的码元，所述生成矩阵B为方形矩阵，所述方法包括：访问存储在第一存储器中的所述k个源码元；从存储在所述第一存储器中的所述源码元形成源列向量S；计算将所述生成矩阵B分解为置换矩阵P、下三角矩阵L和上三角矩阵U的乘积；通过使用所述上三角矩阵U变换所述源列向量S来计算第一经变换的列向量S'，该变换包括所述上三角矩阵U乘所述源列向量S的向下方向上的第一原地矩阵变换，其中从所述源列向量S的第一码元开始并且到S的第n码元结束，用U中的一行与S的当前值的内积来代替S的码元；在所述第一存储器存储所述第一经变换的列向量S'的码元，这些码元替换所述k个源码元中的至少一些；通过使用所述下三角矩阵L变换所述第一经变换的列向量S'来计算第二经变换的列向量S″，该变换包括所述下三角矩阵L乘所述第一经变换的列向量S'的向上方向上的第二原地矩阵变换，其中从所述第一经变换的列向量S'的第一码元开始并且到S'的第n码元结束，用L中的一行与S’的当前值的内积来代替S'的码元；在所述第一存储器存储所述第二经变换的列向量S″的码元，这些码元替换所述第一经变换的列向量S'的码元中的至少一些；通过使用所述置换矩阵P变换所述第二经变换的列向量S″来计算第三经变换的列向量S″′，该变换包括所述置换矩阵P乘所述第二经变换的列向量S″的第三原地矩阵变换，其中从所述第二经变换的列向量S″的第一码元开始并且到S″的第n码元结束，如果(i,P[i])是P中值“1”的位置，则用S″[i]代替S″[P[i]],所述第三经编码的列向量S″′的码元包括所述经编码的码元；以及在所述第一存储器存储所述第三经变换的列向量S″′的码元，这些码元替换所述第二经变换的列向量S″的码元中的至少一些。