线性网络编码把数据包在网络节点的转发过程抽象为有限域上的线性组合，接收端必须根据编码系数矩阵恢复出原始符号。这个恢复过程本质上就是解线性方程组，因此矩阵运算在整个编解码流程中处于核心位置。R语言虽然不是专门的网络仿真工具，但它的矩阵表示、切片操作和丰富的线性代数函数足以支撑一个可读性很高的教学级实现。下文从有限域GF(2)出发，逐步搭建编码器、中间节点转发器和解码器，并讨论随机线性网络编码的解码成功率。

一、线性网络编码为什么可以写成矩阵方程

传统路由节点只能把收到的数据包原样转发，而网络编码允许节点对若干数据包做线性叠加。源节点把要发送的文件切分成m个固定长度的符号，记为X1到Xm，每个符号都属于某个有限域。以最简单的有限域GF(2)为例，每个符号就是一个比特，编码系数gi也取0或1。一个编码包Y可以写成Y=g1X1+g2X2+...+gmXm，其中加法是异或，乘数是按位与。系数向量g=(g1,...,gm)通常随数据包一起发送，接收端无需知道网络拓扑，只需要知道系数向量和收到的编码值。

如果接收端收集到m个编码包，分别表示为Y1,...,Ym，每个包对应一个行向量g_i，把这些行向量堆叠起来就得到m×m的编码矩阵G。此时整个恢复问题可以写成Y=GX。在GF(2)上，只要G是可逆矩阵，源符号向量X就可以通过G的逆矩阵左乘Y得到。正是因为解码过程完全由矩阵求逆或高斯消元决定，线性网络编码才能用R这类矩阵语言简洁实现。R中matrix对象天然支持整行整列操作，用1和0表示有限域元素，就能在不引入额外抽象层的情况下完成全部编解码逻辑。

有限域的选择会直接影响实现复杂度。GF(2)的加法是异或、乘法是与，R原生支持xor函数和&运算符，因此非常适合展示原理。如果需要更高吞吐量，可以使用GF(2^8)等扩展域，这时每个符号是一个字节，加法仍是异或，但乘法不能只用&，需要实现不可约多项式上的乘法。为降低门槛，本文后续示例都在GF(2)上进行，扩展域的方法可以在此基础上把标量运算替换为查表或多项式乘法。

# GF(2) 上的标量运算
add_gf2 <- function(a, b) {
  return(xor(a, b))
}
mul_gf2 <- function(a, b) {
  return(a & b)
}

二、编码器与中间节点的矩阵运算实现

在随机线性网络编码中，源节点为每个输出包选择一组随机系数。R中可以用rbinom函数生成0/1系数，参数prob=0.5表示每个系数为1的概率为0.5。假设源符号个数为4，需要生成6个编码包，那么系数矩阵G的维度就是6×4。因为普通矩阵乘法%*%执行的是实数加法和乘法，它不能直接用于GF(2)，所以必须实现一个基于异或和与运算的矩阵乘法函数gf2_matmul。这个函数按矩阵乘法的定义逐元素计算内积，只是在累加时用xor代替加法，在相乘时用&代替乘法。

下面给出完整的GF(2)矩阵乘法实现。它的输入A是k×m矩阵，B是m×n矩阵，输出k×n矩阵。外层两个循环遍历输出位置，内层循环计算第i行和第j列的内积。GF(2)上内积是各分量相乘后再异或累加，而不是普通求和。这个函数的复杂度是O(k*m*n)，对于教学场景和中小规模网络已经足够，后续如果需要处理大规模数据包，可以再用Rcpp或位运算进行优化。

gf2_matmul <- function(A, B) {
  result <- matrix(0L, nrow = nrow(A), ncol = ncol(B))
  for (i in 1:nrow(A)) {
    for (j in 1:ncol(B)) {
      s <- 0L
      for (k in 1:ncol(A)) {
        s <- xor(s, A[i, k] & B[k, j])
      }
      result[i, j] <- s
    }
  }
  return(result)
}
set.seed(42)
n_symbols <- 4
n_packets <- 6
G <- matrix(rbinom(n_packets * n_symbols, size = 1, prob = 0.5),
            nrow = n_packets, ncol = n_symbols)
X <- c(1L, 0L, 1L, 1L)
Y <- gf2_matmul(G, matrix(X, ncol = 1))
print(Y)

中间节点收到多个编码包后，可以继续生成新的编码包，而不需要解码。假设节点收到两个包(Y1,g1)和(Y2,g2)，它可以选择两个随机系数c1和c2，发送Y'=c1Y1+c2Y2，同时系数向量更新为g'=c1g1+c2g2。这个操作在矩阵层面仍然是一次线性组合。用R实现时，可以先构造一个2×m的局部系数矩阵，再用gf2_matmul与收到的数据段相乘。对于大规模网络，中间节点的这种重新编码能力可以提升吞吐量，因为节点不必等待完整的一代数据就能转发。

需要特别注意的是，全局编码矩阵G会随着网络路径不断变化。源节点看到的是系数矩阵G，经过若干中间节点后，接收端拿到的是G'，但G'仍然是源符号X的线性组合矩阵。接收端能否解码只取决于G'是否满秩，与中间节点具体做了什么组合无关。这个性质正是随机线性网络编码能分布式运行的基础。R代码中把G'记为接收端系数矩阵，后续解码都围绕它展开。

三、基于高斯消元的GF(2)求解器

拿到接收端系数矩阵G'和编码数据向量Y后，直接求逆在GF(2)上并不方便，常用的做法是高斯消元。与实数域不同，GF(2)上的消元没有分数，主元只能是1，消元时把主元行异或到其他行即可。将增广矩阵[G'|Y]化作行简化阶梯形后，最后一列就是源符号向量X。如果矩阵秩不足，说明收集到的编码包存在线性相关，需要继续等待更多包。

下面实现一个gf2_solve函数。函数首先构造增广矩阵，然后逐列寻找主元。在GF(2)中主元值为1，所以可以直接用which函数查找当前列中值为1的行。找到主元后，如果它不在当前处理行，就交换两行；接着对所有其他行，如果该行当前列为1，就把主元行异或到该行，从而把当前列其他位置清零。消元完成后，增广矩阵最后一列即为解。

gf2_solve <- function(A, b) {
  n <- nrow(A)
  aug <- cbind(A, b)
  pivot_row <- 1L
  for (col in 1:n) {
    candidates <- which(aug[pivot_row:n, col] == 1L)
    if (length(candidates) == 0L) next
    pivot <- pivot_row + candidates[1] - 1L
    if (pivot != pivot_row) {
      aug[c(pivot_row, pivot), ] <- aug[c(pivot, pivot_row), ]
    }
    for (row in 1:n) {
      if (row != pivot_row && aug[row, col] == 1L) {
        aug[row, ] <- xor(aug[row, ], aug[pivot_row, ])
      }
    }
    pivot_row <- pivot_row + 1L
    if (pivot_row > n) break
  }
  if (pivot_row <= n) return(NULL)
  return(aug[, n + 1L])
}

调用这个函数需要传入编码矩阵和编码数据向量。即使系数矩阵是可逆的，实数域中的solve(G,Y)也无法得到GF(2)上的正确结果，因为实数求解会得到分数甚至负数。在有限域场景中必须使用专门的消元算法。下面用之前生成的G和Y进行一次解码测试。为了演示，可以构造一个4×4可逆矩阵，或直接从G中选取前4个线性无关行。实际随机编码中，接收端收集到4个包后不一定满秩，所以还要判断返回是否为NULL。

如果求解返回NULL，说明当前包数量不足或线性相关，接收端应继续接收编码包。很多实现会在接收端维护一个动态消元缓冲区，每收到一个新包就把它插入当前系数矩阵进行增量消元，这样可以尽早发现满秩时刻，而不必等所有包到达后一次性求解。R语言的向量化操作让这种增量更新也很容易实现，例如每次用新系数向量消去已有行，再判断当前基底是否达到符号数。

四、随机线性网络编码的解码成功率模拟

随机线性网络编码的解码成功概率与有限域大小和编码包数量密切相关。在GF(2)上，如果接收端恰好收到m个编码包，这m个系数行向量组成的随机矩阵不一定满秩，因此解码可能失败。随着收到的编码包数量增加到m+1、m+2，满秩概率迅速接近1。R语言可以用重复随机试验来估计不同包数量下的解码成功率。构建随机系数矩阵、计算GF(2)上的秩，然后统计满秩比例。

下面给出一个模拟函数estimate_decode_rate。函数为每个试验生成n_packets×n_symbols的随机0/1矩阵，调用gf2_rank计算秩，若秩等于n_symbols则视为成功。gf2_rank可以使用与gf2_solve类似的消元过程，只是不需要右侧向量，只返回主元个数。

gf2_rank <- function(A) {
  m <- nrow(A)
  n <- ncol(A)
  aug <- A
  pivot_row <- 1L
  for (col in 1:n) {
    candidates <- which(aug[pivot_row:m, col] == 1L)
    if (length(candidates) == 0L) next
    pivot <- pivot_row + candidates[1] - 1L
    if (pivot != pivot_row) {
      aug[c(pivot_row, pivot), ] <- aug[c(pivot, pivot_row), ]
    }
    for (row in 1:m) {
      if (row != pivot_row && aug[row, col] == 1L) {
        aug[row, ] <- xor(aug[row, ], aug[pivot_row, ])
      }
    }
    pivot_row <- pivot_row + 1L
    if (pivot_row > m) break
  }
  return(pivot_row - 1L)
}
estimate_decode_rate <- function(n_symbols, n_packets, trials = 1000) {
  success <- 0L
  for (t in 1:trials) {
    G <- matrix(rbinom(n_packets * n_symbols, size = 1, prob = 0.5),
                nrow = n_packets, ncol = n_symbols)
    if (gf2_rank(G) == n_symbols) {
      success <- success + 1L
    }
  }
  return(success / trials)
}
estimate_decode_rate(4, 4)
estimate_decode_rate(4, 5)
estimate_decode_rate(4, 6)

运行这段模拟可以看到，当n_packets等于n_symbols=4时，成功率大约在0.28到0.29左右，这与GF(2)随机4×4矩阵不可逆的概率一致。当编码包数增加到5时，成功率超过0.5；增加到6时接近0.8。如果使用更大的有限域，比如GF(2^8)，则即使包数等于符号数，成功率也会非常接近1，这是实际系统倾向使用8位或更大符号的原因。R中可以通过把矩阵元素设置为0到255的整数，并用自定义的GF(2^8)乘法替换按位与，来模拟更接近真实环境的随机线性网络编码。

性能方面，本文实现的三重循环在包数和符号数较小时足够使用，但如果每代包含数百个符号，纯R的循环会明显变慢。此时可以考虑三个优化方向：一是用整数位表示多个GF(2)元素，把异或和与操作合并到机器字级别；二是用Rcpp把消元核心编译成C++；三是改用已经实现有限域运算的扩展包。对于大多数教学演示和协议验证，本文给出的代码结构清晰、依赖少，已经能够完整展示线性网络编码解码的矩阵运算本质。