反转二进制网络

Question

如何反转二进制方程,以便我可以找到哪些输入将产生给定的输出.

例:

Inputs: i0 through i8
Outputs: o0 through o8
Operators: ^ = XOR, & = AND

二元方程:

(1&i0) ^ (1&i1) ^ (0&i2) ^ (1&i3) ^ (0&i4) ^ (0&i5) ^ (0&i6) ^ (0&i7) ^ (0&i8) = o0
(0&i0) ^ (1&i1) ^ (0&i2) ^ (1&i3) ^ (1&i4) ^ (0&i5) ^ (0&i6) ^ (0&i7) ^ (0&i8) = o1
(0&i0) ^ (1&i1) ^ (1&i2) ^ (0&i3) ^ (0&i4) ^ (1&i5) ^ (0&i6) ^ (0&i7) ^ (0&i8) = o2
(1&i0) ^ (0&i1) ^ (0&i2) ^ (1&i3) ^ (0&i4) ^ (0&i5) ^ (0&i6) ^ (0&i7) ^ (0&i8) = o3
(0&i0) ^ (1&i1) ^ (0&i2) ^ (1&i3) ^ (1&i4) ^ (0&i5) ^ (0&i6) ^ (0&i7) ^ (0&i8) = o4
(0&i0) ^ (0&i1) ^ (0&i2) ^ (0&i3) ^ (0&i4) ^ (1&i5) ^ (0&i6) ^ (0&i7) ^ (0&i8) = o5
(0&i0) ^ (0&i1) ^ (0&i2) ^ (1&i3) ^ (0&i4) ^ (0&i5) ^ (1&i6) ^ (0&i7) ^ (0&i8) = o6
(0&i0) ^ (0&i1) ^ (0&i2) ^ (1&i3) ^ (1&i4) ^ (0&i5) ^ (1&i6) ^ (1&i7) ^ (0&i8) = o7
(0&i0) ^ (0&i1) ^ (0&i2) ^ (0&i3) ^ (0&i4) ^ (1&i5) ^ (0&i6) ^ (0&i7) ^ (1&i8) = o8

以矩阵形式:

1,1,0,1,0,0,0,0,0,1
0,1,0,1,1,0,0,0,0,1
0,1,1,0,0,1,0,0,0,1
1,0,0,1,0,0,0,0,0,1
0,1,0,1,1,0,0,0,0,1
0,0,0,0,0,1,0,0,0,1
0,0,0,1,0,0,1,0,0,1
0,0,0,1,1,0,1,1,0,1
0,0,0,0,0,1,0,0,1,1

附加限制:

• 主要对角线始终为1
• 如果有解决方案,我感兴趣,更多的是解决方案本身

我如何通过算法查找输入i0 -i8,使输出o0-o8为1？我真正想要的是,是否有这样的解决方案.

我需要一种可扩展到更大网络的算法,至少100个输入/输出.

Answer 1

通过XOR(而不是OR),乍一看似乎某种形式的Gauss-Jordan消除可以至少简化问题.通过缩减行梯形表格中的维基百科文章调整伪代码,我们得到:

function ToReducedRowEchelonForm(Matrix M) is
    // 'lead' is the column index in a row of the leading 1
    lead := 0
    rowCount := the number of rows in M
    columnCount := the number of columns in M
    for 0 ? r < rowCount do
        if columnCount ? lead then
            stop
        end if
        i = r
        // Find row with lead point
        while M[i, lead] = 0 do
            i = i + 1
            if rowCount = i then
            // no pivot in this column, move to next
                i = r
                lead = lead + 1
                if columnCount = lead then
                    stop
                end if
            end if
        end while
        Swap rows i and r
        for 0 ? i < rowCount do
            if i ? r do
                Set row i to row i XOR row r
            end if
        end for
        lead = lead + 1
    end for
end function

这会将样本转换为:

1,0,0,0,0,0,0,1,0,0
0,1,0,0,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0
0,0,0,1,0,0,0,1,0,1
0,0,0,0,1,0,0,1,0,0
0,0,0,0,0,1,0,0,0,1
0,0,0,0,0,0,1,1,0,0
0,0,0,0,0,0,0,0,1,0
0,0,0,0,0,0,0,0,0,0

从那里,您可以调整整数分区算法以生成行的可能输入,同时考虑先前行的分区.生成分区是备忘录的理想选择.

仍然需要进行时序分析,看看上述是否值得.