방법 진 방정식 가우스 소거법을 구현하기

Question

난 방정식의 시스템을
1 = x⊕y⊕z
1 = x⊕y⊕w
0 = x⊕w⊕z
1 = w⊕ y⊕z

이 시스템을 해결하기 위해 가우시안 제거를 구현하려고합니다. here으로 나눗셈, 뺄셈 및 곱셈을 XOR로 바꾸지 만 잘못된 대답을줍니다. 정답은 (x, y, z, w)입니다.) = (0,1,0,0)
내가 뭘 잘못하고 있니?

public static void ComputeCoefficents(byte[,] X, byte[] Y) 
    { 
     int I, J, K, K1, N; 
     N = Y.Length; 
     for (K = 0; K < N; K++) 
     { 
      K1 = K + 1; 
      for (I = K; I < N; I++) 
      { 
       if (X[I, K] != 0) 
       { 
        for (J = K1; J < N; J++) 
        { 
         X[I, J] /= X[I, K]; 
        } 
        //Y[I] /= X[I, K]; 
        Y[I] ^= X[I, K]; 

       } 
      } 
      for (I = K1; I < N; I++) 
      { 
       if (X[I, K] != 0) 
       { 
        for (J = K1; J < N; J++) 
        { 
         X[I, J] ^= X[K, J]; 
        } 
        Y[I] ^= Y[K]; 
       } 
      } 
     } 
     for (I = N - 2; I >= 0; I--) 
     { 
      for (J = N - 1; J >= I + 1; J--) 
      { 
       //Y[I] -= AndOperation(X[I, J], Y[J]); 
       Y[I] ^= (byte)(X[I, J]* Y[J]); 

      } 
     } 
    } 

Answer 1

나는 이것을 위해 가우스 제거 모드 2를 적용하려고한다고 생각합니다. 당신의 방정식을 해결하기 위해 Gausian 제거를 사용할 수 있도록

당신의 방정식

a_1 * x + b_1 * y + c_1 * z = d_1 
a_2 * x + b_2 * y + c_2 * z = d_2 
a_3 * x + b_3 * y + c_3 * z = d_3 
a_4 * x + b_4 * y + c_4 * z = d_4 

그리고 Z2 *에서

이 and 인 형태의 경우는, 가우스 소거법 모드 K 작업을 수행 할 수 있습니다 일반적으로

와 +는 xor입니다 형태

x (xor) y (xor) z = 1 
x (xor) y (xor) w = 1 
x (xor) z (xor) w = 0 
y (xor) z (xor) w = 1 

가우스 제거를 손으로 사용하면됩니다.

해당 증강 행렬이다 :

1 1 1 0 | 1 
1 1 0 1 | 1 
1 0 1 1 | 0 
0 1 1 1 | 1 

1 1 1 0 | 1 
0 0 1 1 | 0 (R2 = R2 + R1) 
0 1 0 1 | 1 (R3 = R3 + R1) 
0 1 1 1 | 1 

1 1 1 0 | 1 
0 1 1 1 | 1 (R2 = R4) 
0 1 0 1 | 1 
0 0 1 1 | 0 (R4 = R2) 

1 0 0 1 | 0 (R1 = R1 + R2) 
0 1 1 1 | 1 
0 0 1 0 | 0 (R3 = R3 + R2) 
0 0 1 1 | 0 

1 0 0 1 | 0 
0 1 0 1 | 1 (R2 = R2 + R3) 
0 0 1 0 | 0  
0 0 0 1 | 0 (R4 = R4 + R3) 

1 0 0 0 | 0 (R1 = R1 + R4) 
0 1 0 0 | 1 (R2 = R2 + R4) 
0 0 1 0 | 0  
0 0 0 1 | 0 

은 용액 (X, Y, Z, w) = (0,1,0,0)를주고.

하지만이 작업에는 행 피벗이 필요합니다. 코드에서 볼 수 없습니다.

거기에있을 필요가없는 코드에서 주위에 떠있는 곱셈과 나누기가 있습니다. 코드가 다음과 같이 표시 될 것으로 기대합니다. (TODO를 수정해야합니다).

public static void ComputeCoefficents(byte[,] X, byte[] Y) { 
    int I, J, K, K1, N; 
    N = Y.Length; 

    for (K = 0; K < N; K++) { 
    //First ensure that we have a non-zero entry in X[K,K] 
    if(X[K,K] == 0) { 
     for(int i = 0; i<N ; ++i) { 
     if(X[i,K] != 0) { 
      for(...) //TODO: A loop to swap the entries 
      //TODO swap entries in Y too 
      } 
     } 
    if(X[K,K] == 0) { 
     // TODO: Handle the case where we have a zero column 
     //  - for now we just move on to the next column 
     //  - This means we have no solutions or multiple 
     //  solutions 
     continue 
    } 

    // Do full row elimination. 
    for(int I = 0; I<N; ++I) 
    { 
     if(I!=K){ //Don't self eliminate 
     if(X[I,K]) { 
      for(int J=K; J<N; ++J) { X[I,J] = X[I,J]^X[K,J]; } 
      Y[J] = Y[J]^Y[K]; 
     } 
     } 
    } 
    } 

    //Now assuming we didnt hit any zero columns Y should be our solution. 

}