0

m * nのバイナリ行列A、m * pのバイナリ行列Bが与えられます。ここで、n> m AX=BとなるようにXを計算するための効率的なアルゴリズムは何ですか。

例えば：

A = 
1  1  0  0  1  1  0  1  0  0  
1  1  0  0  1  0  1  0  0  1  
0  1  1  0  1  0  1  0  1  0  
1  1  1  1  1  0  0  1  1  0  
0  1  1  0  1  0  1  1  1  0 

B = 
0  1  0  1  1  0  1  1  0  1  0  0  1  0  
0  0  1  0  1  1  0  0  0  1  0  1  0  0  
0  1  1  0  0  0  1  1  0  0  1  1  0  0  
0  0  1  1  1  1  0  0  0  1  1  0  0  0  
1  0  0  1  0  0  1  0  1  0  0  1  1  0

私がバイナリ行列と言うとき、私は体Z_2で定義された行列を意味することに注意してください。つまり、すべての算術はmod2です。

興味がある場合、これはランダムエラー訂正コードに適した行列を生成する際に私が直面している問題です。

4

1 に答える 1

2

行の削減でそれを行うことができます。Aの右側にBを配置してから、行を（全体として）交換して、行0、列0に1を取得します。次に、その行を列0に「1」がある他の行にxorして、列0に1が1つしかないようにします。次に、次の列に移動します。[1,1]がゼロの場合、行1を1が含まれる後の行と交換し、行をxorして、列内の1つだけにします。'A'が正方行列であり、解が存在すると仮定すると、最終的にAを1に変換し、BをAx=Bの解に置き換えます。n> mの場合、方程式よりも未知数が多いシステムがあるため、いくつかの未知数を解き、他の未知数をゼロに設定できます。行の削減中に、「1」を持つ値が列にない場合

于 2013-02-03T02:49:38.200 に答える