Goto Chapter: Top 1 2 3 4 5 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

5 Multi-Valued Threshold Elements
 5.1 Threshold Elements over GF(p^k)

5 Multi-Valued Threshold Elements

5.1 Threshold Elements over GF(p^k)

Let F=GF(p^k) be a Galois field with primitive element ε and let F^* be the multiplicative group of F. Let us consider all proper subgroups of F^*:

C_{j_1}= \langle \sigma_1 \mid \sigma_1^{j_1}=1 \rangle, \ldots , C_{j_t}= \langle \sigma_t \mid \sigma_n^{j_t}=1 \rangle,

where σ_i=ϵ^frac|F^*|j_i} (i=1,...,t)are the generators of the corresponding cyclic groups. Denote T={ j_1, ..., j_t}. Let G_n = C_k_1⊗ ... ⊗ C_k_n be a direct product of cyclic groups C_k_i (k_i ∈ T,i=1,...,n).

A discrete function of n variables over a finite field F is a mapping f:G_n -> C_q, q ∈ T, C_q = ⟨ σ ∣ σ^q=1 ⟩, σ = ϵ^frac|F^*|q}.

We define the function FSignξ in the following way [Gec10]:

\forall \xi \in F^* : FSign \xi = \sigma^j, \;\; \textrm{if} \;\; \frac{j|F^*|}{q}\leq \textrm{deg}\xi < \frac{(j+1)|F^*|}{q},

in which deg ξ is obtained from the equality ξ=ϵ^deg ξ, j ∈ { 1, ... , q-1 }.

Let (w_1, ..., w_n; T) ∈ F^n+1. For all overlineg = (x_1,...,x_n) ∈ G_n (i.e. x_j ∈ C_k_j) we define

w(\overline{g}) = \sum_{i=1}^n w_i x_i + T \in F.

A neural element with structure vector (w_1, ..., w_n; T) ∈ F^n+1 is a logic device that realizes the function FSign (w(overlineg)) for all overlineg ∈ G_n.

Discrete function f which is relizable by a single neural element over the field F is called neurofunction.

5.1-1 MVThresholdElement
‣ MVThresholdElement( Structure, Dimensions, Field )( function )

For the two-element list Structure, in which the first element is a vector over the field Field, and the second element is an element of the Field, a list of positive integers Dimensions (or an integerm if all the dimensions are equal) and a Galois field Field the function MVThresholdElement returns a multi-valued threshold element with the number of inputs equal to the length of the first element of Structure list.


gap> F:=GF(13);;
gap> st:=[[Z(13)^5,Z(13)^7],Z(13)^4];;
gap> dim:=[2,3,3];;
gap> mvte:=MVThresholdElement(st,dim,F);
< multivalued threshold element over GF(13) with structure [[ 6, 11 ], 3] and
  dimension vector [ 2, 3, 3 ] >
gap> Display(mvte);
Structure vector = [[ 6, 11 ], 3]
Dimension vector = [[ 2, 3, 3 ]]
Field: GF(13)
Multi-Valued Threshold Element realizes the function f :
[ 1, 1 ]  ||  9
[ 1, 3 ]  ||  3
[ 1, 9 ]  ||  1
[ 12, 1 ]  ||  1
[ 12, 3 ]  ||  1
[ 12, 9 ]  ||  9
gap> ## If all dimensions in dimension vector are equal, the user can enter
just this number.
gap> F:=GF(5);;
gap> st:=[[Z(5)^0,Z(5)^0],Z(5)^2];;
gap> dim:=2;;
gap> mvte:=MVThresholdElement(st,dim,F);
< multivalued threshold element over GF(5) with structure [[ 1, 1 ], 4] and
  dimension vector [ 2, 2, 2 ] >
gap> Display(mvte);
Structure vector = [[ 1, 1 ], 4]
Dimension vector = [[ 2, 2, 2 ]]
Field: GF(5)
Multi-Valued Threshold Element realizes the function f :
[ 1, 1 ]  ||  1
[ 1, 4 ]  ||  4
[ 4, 1 ]  ||  4
[ 4, 4 ]  ||  1

The function Display outputs the stucture of the given threshold element mvte and the truth table in given alphabet. In the previous example mvte realizes a three-valued function in { 1, 3, 9 } alphabet over GF(13).

5.1-2 IsMVThresholdElement
‣ IsMVThresholdElement( Obj )( function )

For the object Obj the function IsMVThresholdElement returns true if Obj is a multi-valued threshold element (see MVThresholdElement (5.1-1)), and false otherwise.


gap> IsMVThresholdElement(mvte);
true

5.1-3 OutputOfMVThresholdElement
‣ OutputOfMVThresholdElement( MVThrEl )( function )

For the multi-valued threshold element MVThrEl the function OutputOfMVThresholdElement returns the truth vector of the multi-valued Boolean function, realized by MVThrEl.


gap> F:=GF(13);;
gap> st:=[[Z(13)^5,Z(13)^7],Z(13)^4];;
gap> dim:=[2,3,3];;
gap> mvte:=MVThresholdElement(st,dim,F);
< multivalued threshold element over GF(13) with structure [[ 6, 11 ], 3] and
  dimension vector [ 2, 3, 3 ] >
gap> f:=OutputOfMVThresholdElement(mvte);
< logic function of 2 variables and dimension vector [ 2, 3, 3 ]>
gap> Display(f);
[ 0, 0 ] || 2
[ 0, 1 ] || 1
[ 0, 2 ] || 0
[ 1, 0 ] || 0
[ 1, 1 ] || 0
[ 1, 2 ] || 2

5.1-4 StructureOfMVThresholdElement
‣ StructureOfMVThresholdElement( MVThrEl )( function )

For the multi-valued threshold element MVThrEl the function StructureOfMVThresholdElement returns the structure vector of MVThrEl (see MVThresholdElement (5.1-1)).


gap> StructureOfMVThresholdElement(mvte);
[ [ Z(13)^5, Z(13)^7 ], Z(13)^4 ]

5.1-5 MVBooleanFunctionBySTE
‣ MVBooleanFunctionBySTE( Func, Dim, F )( function )

For the given multi-valued function Func and the prime field F the function MVBooleanFunctionBySTE returns the multi-valued threshold element over F if Func is realizable and an empty list otherwise. The algorithm realizing this function was proposed in [Gec10].


gap> f:=LogicFunction(2,2,[0,1,1,0]);
< Boolean function of 2 variables >
gap> mvte:=MVBooleanFunctionBySTE(f,GF(3));
[  ]
gap> mvte:=MVBooleanFunctionBySTE(f,GF(5));
< multivalued threshold element over GF(5) with structure [[ 1, 1 ], 4] and
  dimension vector [ 2, 2, 2 ] >
gap> Display(last);
Structure vector = [[ 1, 1 ], 4]
Dimension vector = [[ 2, 2, 2 ]]
Field: GF(5)
Multi-Valued Threshold Element realizes the function f :
[ 1, 1 ]  ||  1
[ 1, 4 ]  ||  4
[ 4, 1 ]  ||  4
[ 4, 4 ]  ||  1
gap> ## Consider an example if dimensions are presented as a list.
gap> f:=LogicFunction(2,[2,3,3],[0,0,1,1,2,2]);
< logic function of 2 variables and dimension vector [ 2, 3, 3 ]>
gap> mvte:=MVBooleanFunctionBySTE(f,GF(13));
< multivalued threshold element over GF(13) with structure [[ 12, 10 ], 5]
  and dimension vector [ 2, 3, 3 ] >
gap> Display(last);
Structure vector = [[ 12, 10 ], 5]
Dimension vector = [[ 2, 3, 3 ]]
Field: GF(13)
Multi-Valued Threshold Element realizes the function f :
[ 1, 1 ]  ||  1
[ 1, 3 ]  ||  1
[ 1, 9 ]  ||  3
[ 12, 1 ]  ||  3
[ 12, 3 ]  ||  9
[ 12, 9 ]  ||  9


 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 Bib Ind

generated by GAPDoc2HTML