GF2代码的高斯消元

Question

我有这个 gauss_eliminate 函数，但我不想处理实数，而是希望它处理二进制值。我需要 GF2 gauss_eliminate 函数，其中输入为二进制，输出为二进制。这会产生实际值，而不是二进制值，例如 0.57142857142857 0.71428571428571 -0.42857142857143 -0.28571428571429 0.14285714285714

高斯消元有以下 3 个允许的步骤： 1) 交换两行（为了实现某种外观） 2) 将一行乘以一个非零数， 3）将一行的倍数添加到另一行。 -- 在 GF2 中：加法运算是 XOR : 0+0=0, 0+1=1, 1+0=1, 1+1=0 --and-- 乘法是AND运算：0*0=0,0*1=0,1*0=0,1*1=1

function gauss_eliminate($A, $b, $N)
{
for ($col = 0; $col < $N; $col++) {
    $j = $col;
    $max = $A[$j][$j];

    for ($i = $col + 1; $i < $N; $i++) {
        $tmp = abs($A[$i][$col]);
        if ($tmp > $max) {
            $j = $i;
            $max = $tmp;
        }
    }

    swap_rows($A, $b, $col, $j);

    for ($i = $col + 1; $i < $N; $i++) {
        $tmp = $A[$i][$col] / $A[$col][$col];
        for ($j = $col + 1; $j < $N; $j++) $A[$i][$j] -= $tmp * $A[$col][$j];
        $A[$i][$col] = 0;
        $b[$i] -= $tmp * $b[$col];
    }
}
$x = array();
for ($col = $N - 1; $col >= 0; $col--) {
    $tmp = $b[$col];
    for ($j = $N - 1; $j > $col; $j--) $tmp -= $x[$j] * $A[$col][$j];
    $x[$col] = $tmp / $A[$col][$col];
}
return $x;
}

新代码 #1，仍然无效：

function gauss_eliminate($A, $b, $N)
{
for ($col = 0; $col < $N; $col++) {
    $j = $col;
    $max = $A[$j][$j];

    for ($i = $col + 1; $i < $N; $i++) {
        $tmp = abs($A[$i][$col]);
        if ($tmp > $max) {
            $j = $i;
            $max = $tmp;
        }
    }

    swap_rows($A, $b, $col, $j);

    for ($i = $col + 1; $i < $N; $i++) {
        for ($j = $col + 1; $j < $N; $j++) 
          $A[$i][$j]=( $A[$i][$j] != $A[$col][$j] ) ? 1 : 0;
        $A[$i][$col] = 0;
        $b[$i]=( $b[$i] != $b[$col] ) ? 1 : 0;
    }
}
$x = array();
for ($col = $N - 1; $col >= 0; $col--) {
#        $tmp = $b[$col];    
#        for ($j = $N - 1; $j > $col; $j--) $tmp -= $x[$j] * $A[$col][$j];
    $x[$col] = ( $x[$col] != $A[$col][$j] ) ? 1 : 0;
}
return $x;
}

新代码 #2 - 仍然无效 - tmp 设置为备用

function gauss_eliminate($A, $b, $N)
{ 
for ($col = 0; $col < $N; $col++) {
    $j = $col;
    $max = $A[$j][$j];

    for ($i = $col + 1; $i < $N; $i++) {
        $tmp = abs($A[$i][$col]);
        if ($tmp > $max) { $j = $i; $max = $tmp; }
    }
    swap_rows($A, $b, $col, $j);

    for ($i = $col + 1; $i < $N; $i++) {
#            $tmp = $A[$i][$col] / $A[$col][$col];
        for ($j = $col + 1; $j < $N; $j++) $A[$i][$j]=($A[$i][$j] != $A[$col][$j] ? 1 : 0);
        $A[$i][$col] = 0;
        $b[$i] = ( $b[$i] != $b[$col] ? 1 : 0);
    }
}
$x = array();
for ($col = $N - 1; $col >= 0; $col--) {
    $tmp = $b[$col];
    for ($j = $N - 1; $j > $col; $j--) $tmp = 1 - $tmp;
    $x[$col] = ($tmp != $A[$col][$j] ? 1 : 0);
}
return $x;
}

Answer 1

看来我找到了正确的语法。在以一种有意义的方式修改代码后，我得到了一个示例的正确结果……将 - 转换为 +，并将此 + 转换为 XOR，而 / 被忽略并且 * 是 AND。如果能确认此代码是正确的，那就太好了。

function gauss_eliminate($A, $b, $N) {
for ($col = 0; $col < $N; $col++) {
    $j = $col;
    $max = $A[$j][$j];

    for ($i = $col + 1; $i < $N; $i++) {
        $tmp = abs($A[$i][$col]);
        if ($tmp > $max) {
            $j = $i;
            $max = $tmp;
        }
    }
    swap_rows($A, $b, $col, $j);

    for ($i = $col + 1; $i < $N; $i++) {
#            $tmp = $A[$i][$col] / $A[$col][$col];
#            for ($j = $col + 1; $j < $N; $j++) {
#                $A[$i][$j] -= $tmp * $A[$col][$j];
#            }
#            $A[$i][$col] = 0;
#            $b[$i] -= $tmp * $b[$col];
        $tmp = $A[$i][$col];
        for ($j = $col + 1; $j < $N; $j++) {  
#                $A[$i][$j] = $A[$i][$j] + ( $tmp * $A[$col][$j] );
            $A[$i][$j] = ( $A[$i][$j] != ( $tmp && $A[$col][$j] ) ) ? 1 : 0;
        }
        $A[$i][$col] = 0;
#            $b[$i] = $b[$i]  + ($tmp * $b[$col]);
        $b[$i] = ( $b[$i] != ($tmp && $b[$col]) ) ? 1 : 0;
    }
}
$x = array();
for ($col = $N - 1; $col >= 0; $col--) {
    $tmp = $b[$col];
    for ($j = $N - 1; $j > $col; $j--) {
#            $tmp -= $x[$j] * $A[$col][$j];
#            $tmp = $tmp + ($x[$j] * $A[$col][$j]);
        $tmp = ( $tmp != ($x[$j] && $A[$col][$j]) ) ? 1 : 0;
    }  
#        $x[$col] = $tmp / $A[$col][$col];
    $x[$col] = $tmp;
}
return $x;
}

注释文本是旧的（非 GF2 代码）以及我的 "middle step" 显示我将 + 转换为 XOR、* 转换为 AND 等的地方

GF2代码的高斯消元

Gaussian Eliminate for GF2 code

php

gaussian