倍频程:群上的矩阵乘法

我认为用有限组可能的值和非标准的加法和乘法进行算术运算最有效的方法是查表。

表查找要求对矩阵进行编码,使元素成为组元素列表中的索引。由于索引从1开始,所以需要将{0,1,x,x+1}表示为{1,2,3,4}。

但除了1=0、2=1的笨拙映射之外,查表的过程非常简单。这是我编造的一些示例代码,它似乎有效,但我可能犯了一些错误(并且我可能误解了确切的算术规则):

function out = group_mtimes(lhs,rhs)
[I,K] = size(lhs);
[K2,J] = size(rhs);
if K~=K2, error('Inner dimensions must agree'), end

out = zeros(I,J);
for j=1:J
   for i=1:I
      v = 1;
      for k=1:K
         v = group_scalar_add(v, group_scalar_times(lhs(i,k),rhs(k,j)));
      end
      out(i,j) = v;
   end
end

disp('lhs = ')
group_print(lhs)
disp('rhs = ')
group_print(rhs)
disp('lhs * rhs = ')
group_print(out)

end

function group_print(in)
names = {'0','1','x','1+x'};
disp(names(in)) % Quick-and-dirty, can be done much better!
end

function out = group_scalar_add(lhs,rhs)
table = [
   1,2,3,4
   2,1,4,3
   3,4,1,2
   4,3,2,1
   ];
out = table(lhs,rhs);
end

function out = group_scalar_times(lhs,rhs)
table = [
   1,1,1,1
   1,2,3,4
   1,3,4,2
   1,4,2,3
   ];
out = table(lhs,rhs);
end

例如:

>> lhs=[1,2,3,4;2,3,1,4]';
>> rhs=[2,3;4,1];
>> group_mtimes(lhs,rhs);
lhs = 
    '0'      '1'  
    '1'      'x'  
    'x'      '0'  
    '1+x'    '1+x'

rhs = 
    '1'      'x'
    '1+x'    '0'

lhs * rhs = 
    '1+x'    '0'
    '0'      'x'
    'x'      '0'
    'x'      '1'

此代码中没有输入检查,如果输入包含5,您将获得和索引超出范围错误。

正如我在评论中提到的,您可以创建一个类来封装这种类型的数组。然后你可能会超载 plus , times 和 mtimes (针对操作员 + , .* 和 * ,以及 disp 正确写出数值。您可以定义构造函数,以便此类的对象始终具有有效值,这将防止查找表索引错误。这样的类将使使用这些函数变得更加简单。

对于偶数特征的伽罗瓦场的特殊情况,如F4,您可以使用Octave Forge的通信包提供的功能:

• Functions reference: Galois Fields of Even Characteristic

奇数字符的伽罗瓦字段尚未实现:

• Functions reference: Galois Fields of Odd Characteristic