反相二进制网络 [英] Inverting binary networks

问题描述

我如何反转一个二元一次方程，这样我可以找到哪些输入产生一个给定的输出。

How can I invert a binary equation, such that I can find which inputs will produce a given output.

例如：

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？如果有这样的解决方案，或不是​​我真的想找到的。

How can I, algorithmically find inputs i0 -i8 such that outputs o0 - o8 are 1? What I really want to find is if there is such a solution or not.

我需要的算法是可扩展到更大的网络，至少到100的输入/输出

I need an algorithm which is scalable to larger networks, at least up to 100 inputs/outputs.

推荐答案

使用XOR（而不是OR），似乎乍一看某种形式的高斯 - 约旦消去至少可以简化问题。从减少行阶梯形式维基百科的文章适应伪code，我们得到：

With XOR (rather than OR), it seems at first glance that some form of Gauss–Jordan elimination can at least simplify the problem. Adapting the pseudocode from the Wikipedia article on reduced row echelon form, we get:

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

从那里，你可以适应一个整数分割算法生成可能的输入为一排，同时在考虑到该分区previous行。生成一个分区是记忆化的最佳候选。

From there, you could adapt an integer partitioning algorithm to generate the possible inputs for a row, taking in to account the partitions for previous rows. Generating a partition is a great candidate for memoization.

仍然需要做一个时序分析，看看上面是值得的。

Still need to do a timing analysis to see if the above is worthwhile.

这篇关于反相二进制网络的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！