Open access peer-reviewed chapter

Non Classical Structures and Linear Codes

Written By

Surdive Atamewoue Tsafack

Reviewed: 29 March 2021 Published: 11 August 2021

DOI: 10.5772/intechopen.97471

From the Edited Volume

Coding Theory - Recent Advances, New Perspectives and Applications

Edited by Sudhakar Radhakrishnan and Sudev Naduvath

Chapter metrics overview

200 Chapter Downloads

View Full Metrics

Abstract

This chapter present some new perspectives in the field of coding theory. In fact notions of fuzzy sets and hyperstructures which are consider here as non classical structures are use in the construction of linear codes as it is doing for fields and rings. We study the properties of these classes of codes using well known notions like the orthogonal of a code, generating matrix, parity check matrix and polynomials. In some cases particularly for linear codes construct on a Krasner hyperfield we compare them with those construct on finite field called here classical structures, and we obtain that linear codes construct on a Krasner hyperfield have more codes words with the same parameters.

Keywords

  • Linear codes
  • Fuzzy set
  • Krasner hyperstructures
  • Fuzzy logic
  • Algebraic hyperstructures

1. Introduction

In mathematics, non classical structures as fuzzy sets and algebraic hyperstructures approach better many well known real life situation, and represent natural extension of classical algebraic structures.

Regarding fuzzy sets theory (fuzzy logic), this was introduced in the middle of 1960 by Lotfi Zadeh [1]. This concept is considered today as one of the most important of the second half of twentieth century, this in view of its applications in technological sciences and the impressive quantities of paper and book related to it.

As for algebraic hyperstructures, they were introduced by a french mathematician F. Marty [2] in 1934. Since then, more than a thousand papers and several book have been written on this topic. A well known type of algebraic hyperstructures is due to Krasner [3], who used as a technical tool in a study of his on the approximation of valued fields. In the literature they are called Krasner hyperrings and Krasner hyperfields.

Transmission on coding theory always suppose to encode its information and decode the received information, this is what the classical coding theory introduced in 1948 by C. Shannon [4] deals with. It should ne noted that the handling information are certains. So how can we do if the informations are uncertain? Thus as a new perspective for the algebraic coding, we present below a connection between fuzzy sets, Krasner hyperstructures and linear codes, and we find out how they can bring more in classical coding theory.

Advertisement

2. Fuzzy linear codes over Zpk

2.1 Preliminaries

The theory of fuzzy code as we present here were introduce by Shum and Chen De Gang [5], although they have authors such as Hall Diall and Von Kaenel [6, 7] who also worked on it. In this section, we shall formulate the preliminary definitions and results that are required for a good understanding of the sequel (we can see it in [8, 9, 10]).

Definition 2.1. Let X be a non-empty set, let I and J be two fuzzy subsets in X, then:

  • IJx=minIxJx, IJx=maxIxJx,

  • I=J if and only if Ix=Jx, IJ if and only if IxJx,

  • I+Jx=maxIyJzx=y+z, IJx=maxIyJzx=yz.

These for all x,y,zX.

Let denoted by M the Zpk-module Zpkn, where p is a prime integer and n,kN\0.

The following definitions on the fuzzy linear space derive from [11, 12].

Definition 2.2. We called a fuzzy submodule of M, a fuzzy subset F of a Zpk-module M such that for all x,yM and rZpk, we have:

  • Fx+yminFxFy.

  • FrxFx.

Definition 2.3. Let F be a fuzzy subset of a nonempty set M. For t01, we called the the upper t-level cut and lower t-level cut of F, the sets Ft=xMFxt and Ft¯=xMFxt respectively.

Proposition 2.4. F is a fuzzy submodule of an Zpk-module M if and only if for all α,βZpk; x,yM, we have Fαx+βyminFxFy.

The following difinition recalled the notion on fuzzy ideal of a ring.

Definition 2.5. We called a fuzzy ideal of Zpk, a fuzzy subset I of a ring Zpk such that for each x,yZpk;

  • IxyminIxIy.

  • IxymaxIxIy.

Definition 2.6. Let G be a group and R a ring. We denote by RG the set of all formal linear combinations of the form α=gGagg (where agR and ag=0 almost everywhere, that is only a finite number of coefficients are different from zero in each of these sums).

Definition 2.7. Let RG a ring group which is the group algebra of <x> on the ring Zpk (where x is an invertible element of Zpk). A fuzzy subset I of RG is called a fuzzy ideal of RG, if for all α,β RG,

  • IαβmaxIαIβ.

  • IαβminIαIβ.

When we use the transfer principle in [13], we easily get the next Proposition.

Proposition 2.8. A is a fuzzy ideal of RG if and only if for all t01, if At, then At is an ideal of RG.

The following is very important, the give the meaning of the linear code over the ring Zpk.

Definition 2.9. A submodule of Zpkn, is called a linear code of length n over Zpk. (with n a positive integer).

Contrary to the vector spaces, the module do not admit in general a basis. However it possesses a generating family and therefore a generating matrix, but the decomposition of the elements on this family is not necessarily unique.

Definition 2.10. We called generating matrix of a linear code over Zpk all matrix of MZpk, where the lines are the minimal generating family of code.

The equivalence of two codes is define by the following definition.

Definition 2.11. Let Cpk and Cpk two linear codes over Zpk of generating matrix G and G respectively. The codes Cpk and Cpk are equivalences if there exists a permutation matrix P, such that G=GP.

To define a dual of a code which is helpful when we fine some properties of the codes, we need to know the inner product.

Definition 2.12. Let Cpk be a linear code of length n over Zpk, the dual of the code Cpk that we note Cpk is the submodule of Zpkn define by; Cpk={a for all bCpk,a.b=0}. where “” is the natural inner product on the submodule Zpkn.

In a linear code Cpk of length n over Zpk, if for all a0an1Cpk, then sa0an1Cpk (where s is the shift map), then the code is said to cyclic.

2.2 On fuzzy linear codes over Zpk

Now we bring fuzzy logic in linear codes and introduce the notion of fuzzy linear code over the ring Zpk.

Definition 2.13. Let M=Zpkn be a Zpk-module. The fuzzy submodule F of M is called fuzzy linear code of length n over Zpk.

Using the transfer principle of Kondo [13], we have what is follow.

Proposition 2.14. Let A be a fuzzy set on Zpkn.

A is a fuzzy linear code of length n over Zpk if and only if for any t01, if At, then At is a linear code of length n over Zpk.

Corollary 2.15. Let A be a fuzzy set on Zpkn.

A is a fuzzy linear code of length n over Zpk if and only if the characteristic function of any upper t-level cut At for t01 is a fuzzy linear code of length n over Zpk.

Example 2.16. Consider a fuzzy subset F on Z4 as follows:

F:Z401, x1ifx=0;13ifx=1;13ifx=2;13ifx=3..

Then F is a fuzzy submodule on Z4-module Z4, hence F is a fuzzy linear code over Z4.

Remark 2.17. Let F be a fuzzy linear code of length n over Zpk, since Zpkn is a finite set, then ImF=FxxZpkn is finite. Let ImF is set as: t1>t2>>tm (where ti01) that is ImF have m elements.

Since Fti is a linear code over Zpk, let Gti his generator matrix, F can be determined by m matrixes Gt1, Gt2, , Gtm as in the below Theorem 2.31.

There are some know notions of the orthogonality in fuzzy space, but no one of them does not hold here because these definitions does not meet the transfer principle in the sense of the orthogonality for the t-level cut sets. So we have to introduce an new notion of orthogonality on fuzzy submodules.

Definition 2.18. Let F1 and Fu2 be two fuzzy submodules on module Zpkn over the ring Zpk. We said that F1 and F2 are orthogonal if ImF2=1ααImF1 and for all t01, F21t=F1t={yZpkn<x,y>=0, for all xF1t}. Where <,> is the standard inner product on Zpkn.

Noted that F1F2 means F1 and F2 are orthogonal. We what is follow as an example.

Example 2.19. Consider the two fuzzy submodules F1 and F2 on Z4 defined as follows:

F1:Z401, x12ifx=0;14ifx=1;13ifx=2;14ifx=3. and F2:Z401, x34ifx=0;12ifx=1;23ifx=2;12ifx=3..

We easily observe that:

F112=0 and F212=Z4,

F114=Z4 and F134=0,

F113=02 and F123=02.

Thus F1F2.

Remark 2.20. Let F1 be a fuzzy submodule on module Zpkn such that xZpkn, F1x=γ (with γ01), then it does not exists a fuzzy set F on Zpkn such that F1F.

The previous Remark 2.20 show that the orthogonal of some fuzzy submodule in our sense does not always exists, so it is important to see under which condition the orthogonal of fuzzy submodule exists. The following theorem show the existence of the orthogonal of some fuzzy submodule.

Theorem 2.21. Let F1 be a fuzzy submodule on a finite module Zpkn. If ImF1 have more that one element and for all ςImF1 there exist ϵImF1 such that Aς=Aϵ, then there always exists a fuzzy submodule F2 on Zpkn such that F1F2.

Proof. Let F1 be a fuzzy submodule on Zpkn. Assume that ImF1=m>1 and for any ςImA there exist ϵImF1 such that F1ς=F1ϵ.

Assume that ImF1=t1>t2>>tm. Let the sets Mi=xZpknF1x=ti, i=1,,m. These sets form a partition of Zpkn.

Let us define a fuzzy set F as follow:

F:Zpkn01, x1tmi+1, if xMi.

Since ImF1=t1>t2>>tm, we have F1t1F1t2F1tm. As for any ςImF1 there exist ϵImA such that Aς=Aϵ, then Ati=Atmi+1.

Thus F1tmi+1=xZpknFx1tmi+1=MiMi1M1=F1ti=F1tmi+1.

Then by taken F2=F we obtain the need fuzzy submodule.

When the orthogonality exist, there is unique. We have the following theorem to show it.

Theorem 2.22. Let F1, F2 and F3 be three fuzzy submodules on module Zpkn, such that F1F2 and F1F3, then F2=F3.

Proof. Consider that F1F2 and F1F13.

Let t01, and bF21t, then <a,b>=0, for all aF1t. Thus bF31t and F21tF31t. Therefore F3tF3t.

In the same way, we show that F2tF3t. Therefore F2=F3.

Corollary 2.23. The orthogonal of a fuzzy set on Zpkn is a fuzzy submodule on Zpkn.

The orthogonality is an indempotent operator, in fact if F be a fuzzy submodule on Zpkn then F=F1.

The notion of equivalence on fuzzy linear code can be define as follow.

Definition 2.24. Let F1 and F2 be two fuzzy linear codes over Zpk. F1 and F2 are said to be equivalent if for all t01, the linear codes F1t and F2t are equivalent.

Example 2.25. Let CG1 and CG2 be two equivalent linear codes of length n over Zpk.

We define the equivalent fuzzy linear codes as follow:

F1:Zpkn01, x1ifxCG1;0otherwise. and.

F2:Zpkn01, x1ifxCG2;0otherwise..

Thus the 1 and 0 -level cut of the both fuzzy linear codes give F11=CG1 and F21=CG2,

F10=Zpkn and F20=Zpkn.

Remark 2.26. Two equivalent fuzzy linear codes over Zpk have the same image.

2.3 Fuzzy linear codes in a practical way

As we have said in the introduction, how fuzzy linear code can deal with uncertain information in a practical way? This subsection allow us to use directly fuzzyness in the information theory.

Let us draw the communication channel as follows:

FkEncodingFnChannelRnDecodingFk

Assume that Rk=Z22 and Rn=Z23, that means that k=2 and n=3. Let CR3 be a linear code over R, in the classical case, when we send a codeword a=101C through a communication channel, the signal receive can be read as a=0.98,0.03,0.49 and modulate to a=100. Thus to know if a belong to the code C, we use syndrome calculation [14]. Since the modulation have gave a wrong word, we can consider that a have more information than a, in the sense that we can estimate a level to which a word 0 is modulate to 1, and a word 1 is modulate to 0. Therefore it is possible to use the idea of fuzzy logic to recover the transmit codeword.

Let C be a linear code over Z23. To each aC, we find t01 such that t estimate the degree of which the element of R3, obtain from a through the transmission channel belong to the code C. Thus in Z23 the information that we handle are certain, whereas in R3 there are uncertain. When we associate to all elements of Z23 the degree of which its correspond element obtain through the transmission channel belong to Z23, then we obtain a fuzzy code. If the fuzzy code are fuzzy linear code, then we can recover the code C just by using the upper t-level cut. Thus we deal directly with the uncertain information to obtain the code C.

The following example illustrate this reconstruction of the code by using uncertain information in the case of fuzzy linear code.

Example 2.27. Let Z23=000,001,010,100,110,101,011,111 and C=000,001,110,111 be a linear code over Z2.

Assume that after the transmission we obtain respectively 0000.01,011.01,101.001,1,0.999. Let F:Z2301 such that x1ifx=000;0.99ifx=001;0.9ifx=010;0.9ifx=100;0.99ifx=110;0.9ifx=101;0.9ifx=011;0.99ifx=111..

Then by finding a t01 such that Ft=xZ23Fxt=C, we obtain t>0.9. Thus, for t=0.99, we are sure that the receive codeword is in C.

It should be better to investigate in deep this approach.

2.4 Fuzzy cyclic code over Zpk

Let the module Zpkn, in this subsection we will consider the case where the integers n and p are coprime.

Definition 2.28. A fuzzy module F on the module Zpkn is called a fuzzy cyclic code of length n over Zpk if for all a0a1an1Zpkn, then Fan1a0an2Fa0a1an1.

The following proposition give a caracterization of the fuzzy cyclic codes.

Proposition 2.29. [15] A fuzzy submodule F on on Zpkn is a fuzzy cyclic code if and only if for all.

a0a1an1Zpkn, we have Fa0a1an1=Fan1a0an2==

Fa1a2an1a0.

Proposition 2.30. F is a fuzzy cyclic code of length n over Zpk if and only if for all t01, if Ft, then Ft is a ideal of the factor ring ZpkXXn1.

Proof. Assume that F is a fuzzy cyclic code over Zpk and t01 such that Ft. Then Ft is a cyclic code over Zpk.

Let ψ:ZpknZpkXXn1, c¯=c0cn1ψc¯=i=0n1ciXi.

It is prove by easy way that ψ is a isomorphism of Zpk-module, which send a cyclic codes over Zpk onto the ideals of the factor ring ZpkXXn1. Therefore, t01, Ft is a ideal of ZpkXXn1.

Conversely, assume that, t01 such that Ft, Ft is a ideal of factor ring ZpkXXn1. Since Ft is a ideal of factor ring ZpkXXn1, then Ft is a submodule of Zpk-module Zpkn. Hence Ft, is a linear code over Zpk, then F is a fuzzy linear code. Due to ψ, t01, Ft is a cyclic code over Zpk, then F is a fuzzy cyclic code over Zpk.

Since Zpk is a finite ring, then ImF=Fx01xZpkn is also finite. Assume that ImF=t1>t2>>tm, then Ft1Ft2Ftm1Atm=Zpkn.

Let gikXZpkX the generator polynomial of Fti, note that gikX is the Hensel lifting of order k of some polynomial giXZpX which divide Xn1, the cyclic code <gikX>ZpkXXn1 is called the lifted code of the cyclic code <giX>ZpXXn1 [8].

Since Ft1Ft2Ftm1Ftm=Zpkn, then gi+1kXgikX, i=1,,m1. So we define the polynomial hikX=Xn1/gikX which is called the check polynomial of the cyclic code Fti=<gikX>, i=1,,m.

Theorem 2.31. Let G=g1kXg2kXgmkX be a set of polynomial in ZpkX, such that giX divide Xn1, i=1,,m. If gi+1kXgikX for i=1,2,,m1 and <gmkX>=Zpkn, then the set G can determined a fuzzy cyclic code F and <gikX>i=1m is the family of upper level cut cyclic subcodes of F.

The proof is leave for the reader but he can check it in [15].

Advertisement

3. Fuzzy Zpk-linear code

In the previous section, we study define and fuzzy linear codes over the ring Zpk in the previous section. Now define the notion on fuzzy Gray map, we are going to use it in the construction of the fuzzy Zpk-linear codes which is different from the fuzzy linear codes over the ring Zpk.

3.1 Fuzzy Gray map

When we order and enumerate a binary sequences of a fixed length we obtain the code of Gray in it original form. For the length two which interest us directly we have the following Gray code:

000101211310.

Let ϕ:Z22Z22 the Gray map.

Using the extension principle [16], we will define the fuzzy Gray map between two fuzzy spaces by what is follow.

Definition 3.1. Consider the Gray map ϕ:Z22Z22. Let FZ22, FZ22 the set of all the fuzzy subset on Z22 and Z22 respectively. The fuzzy Gray map is the map ϕ̂:FZ22FZ22, such that for all FFZ22, ϕ̂Fy=supAxy=ϕx.

The next Theorem is straightforward.

Theorem 3.2. The fuzzy Gray map ψ̂ is a bijection.

Proof: It is due to the fact that ψ is one to one function.

As in crisp case, we have the following Proposition which is very important.

Proposition 3.3. If F is a fuzzy linear code over Z22 and ϕ the Gray map, then ϕ̂F is no always a fuzzy linear code over the field Z2.

The Gray map give a way to construct the nonlinear codes as binary image of the linear codes, we have for example the case of Kerdock, Preparata, and Goethals codes which have very good properties and also useful (We refer reader for it on [17, 18]). Moreover if C is a linear code of length n over Z4, then C=ψC is a nonlinear code of length 2n over Z2 in generally [18]. In that way we construct a fuzzy Kerdock code in the following example.

Example 3.4. Let G=10002111010012130010132100011132 be a generating matrix for a linear code C of length 8 over Z4. Then his image under the Gray map ϕ give a Kerdock code C.

Let F:Z4801, x1,ifxC;0,otherwise. Thus F is a fuzzy linear code over Z4.

Since ϕ is a bijection, we construct ϕ̂F:Z21601, y1,yE;0,otherwise.,

where E={yZ216y=ϕx and xC}.

Noted that as E is not a linear code over Z2, then ϕ̂Fu is a fuzzy Z2-linear code but not a fuzzy linear code over Z2.

ϕ̂F is a fuzzy Kerdock code of length 16.

By the Example, we remark that a fuzzy Z4-linear code is not in generally a fuzzy linear code over Z2.

If we define the fuzzy binary relation Rϕ on Z22×Z22 by Rϕxy=1,ify=ψx;0,otherwise. It is easy to see [19] that ϕ̂Fy=supFxy=ϕx can be represented by ϕ̂Fy=supminFxRϕxyxZ22.

We now define fuzzy generalized gray map. First we consider the generalized Gray map as in [8] Φ:ZpkZppk1.

Definition 3.5. The map Φ̂:FZpkFZppk1, such that for any FFZpk,

Φ̂Fy=supFxy=Φx,ifasuchxexists;0,otherwise.

Is called a fuzzy generalized gray map.

Remark 3.6.

  1. The Definition 3.5 can be simply write Φ̂Ay=Fx,ify=Φx;0,otherwise. This because Φ:ZpkZppk1 cannot give more than one image for one element.

  2. Let F1FZppk1 such that F1y=t0 for any yZppk1. There does not exist a fuzzy subset FFZpk such that Φ̂F=F1.

Thus Φ̂ is not a bijection map.

3.2 Fuzzy Zpk-linear code

In the following, we will note Φ̂ the map on FZpkn onto FZpn.pk1 which spreads the fuzzy generalized Gray map.

Let define fuzzy Zpk-linear code.

Definition 3.7. A fuzzy code Fu over Zp is a fuzzy Zpk-linear code if it is an image under the fuzzy generalized Gray map of a fuzzy linear code over the ring Zpk.

For a fuzzy Zpk-linear code, if it is the image under the generalized Gray map of a cyclic code over the ring Zpk. Then the fuzzy code Fu is called a fuzzy Zpk-cyclic code.

Remark 3.8. A fuzzy Zpk-linear code is a fuzzy code over the fields Zp.

Example 3.9.

LetF:Z2601,w=abcdef1,ife=f=0;0,otherwise.

F is a fuzzy linear code of length 6 over Z2.

LetF:Z4301,v=xyz1,ifz=0;0,otherwise.

F is a fuzzy linear code of length 3 over Z4.

Since F=ϕ̂F. Then F is a fuzzy Z4-linear code.

Using crisp case technic we prove he following Proposition.

Proposition 3.10. Let Fu be a fuzzy Zpk-linear code, then Fu is no always a fuzzy linear code over the field Zp.

Proof. The need here is to construct an counter-example, which is done in the Example 3.9.

The following diagram give a construct the fuzzy Zpk-linear code. This holds because the fuzzy generalized Gray map image of fuzzy linear code can be a fuzzy linear code over the field Zp:

We construct some codes using the both methods.

Example 3.11.

1. Let F:Zpkn01 be a linear code such that F have three upper t-level cut Ft3Ft2Ft1. Let Ft3=ΦFt3, Ft2=ΦFt2 and Ft1=ΦFt1, we have Ft3=ΦFt3Ft2=ΦFt2Ft1=ΦFt1. We construct F=Φ̂F as follow:

F:Zpn.pk101, yt3,ifyFt3;t2,ifyFt2;t1,ifyFt1;0,otherwise.

2. Let F:Z401, x12ifx=0;13ifx=2;14ifx=1,3.

be a fuzzy linear code over Z4. Then F12=0, F13=02 and F14=Z4.

We construct F12=00, F13=0011 and F14=Z22, the Gray map image of F12, F13 and F14 respectively, we define

F:Z2201,y12ifxF12,y=ϕx;13ifxF13\F12,y=ϕx;14ifxF14\F13,y=ϕx.

We obtain the same code F and ϕ̂F.

Proposition 3.12. [15] If for all t01, Ft=ΦFt (when Ft) is a linear code over Zp, then this two constructions of the fuzzy Zp-linear code above are give the same fuzzy code.

Proof. This follows directly from the definition of the fuzzy generalized Gray map and the fact that the image under the generalized Gray map of a linear code is not a linear code in general.

Advertisement

4. Linear codes over Krasner hyperfields

4.1 Preliminaries

This section recall notions and results that are required in the sequel. All of this can also be check on [3, 20, 21, 22].

Let H be a non-empty set and PH be the set of all non-empty subsets of H. Then, a map :H×HPH, where h1h2h1h2H is called a hyperoperation and the couple H is called a hypergroupoid.

For all non-empty subsets A and B of H and hH, we define AB=aA,bBab, Ah=Ah and hB=hB.

Definition 4.1. A canonical hypergroup R is an algebraic structure in which the following axioms hold:

  1. For any x,y,zR, xyz=xyz,

  2. For any x,yR, xy=yx,

  3. There exists an additive identity 0R such that 0x=x for every xR.

  4. For every xR there exists a unique element x (an opposite of x with respect to hyperoperation “”) in R such that 0xx,

  5. For any x,y,zR, zxy implies yxz and xzy.

Remark 4.2. Note that, in the classical group R+, the concept of opposite of xR is the same as inverse.

A canonical hypergroup with a multiplicative operation which satisfies the following conditions is called a Krasner hyperring.

Definition 4.3. An algebraic hyperstructure R, where “” is usual multiplication on R, is called a Krasner hyperring when the following axioms hold:

  1. R is a canonical hypergroup with 0 as additive identity,

  2. R is a semigroup having 0 as a bilaterally absorbing element,

  3. The multiplication “” is both left and right distributive over the hyperoperation “”.

A Krasner hyperring is called commutative (with unit element) if R is a commutative semigroup (with unit element) and such is denoted R,0,1.

Definition 4.4. Let R,0,1 be a commutative Krasner hyperring with unit such that R\01 is a group. Then, R,0,1 is called a Krasner hyperfield.

This Example is from Krasner.

Example 4.5. [?] Consider a field F+ and a subgroup G of F\0. Take H=F/G=aGaF with the hyperoperation and the multiplication given by:

aGbG=c¯=cGc¯aG+bGaGbG=abG

Then H is a Krasner hyperfield.

We now give an example of a finite hyperfield with two elements 0 and 1, that we name F2 and which will be used it in the sequel.

Example 4.6. Let F2=01 be the finite set with two elements. Then F2 becomes a Krasner hyperfield with the following hyperoperation “” and binary operation “”.

01
001
1101

and

01
000
101

Let R be a hyperring, A and B be a non-empty subset of R. Then, A is said to be a subhyperring of R if (A,,) is itself a hyperring. A subhyperring A of a hyperring R is a left (right) hyperideal of R if raA (arA) for all rR, aA. Also, A is called a hyperideal if A is both a left and a right hyperideal. We define AB by AB={xxab for some aA,bB} and the product AB is defined by AB={xxi=1naibi, with aiA,biB,nN}. If A and B are hyperideals of R, then AB and AB are also hyperideals of R.

Definition 4.7. An algebraic structure R (where and are both hyperoperations) is called additive-multiplicative hyperring if the satisfies the following axioms:

  1. R is a canonical hypergroup with 0 as additive identity,

  2. R is a semihypergroup having 0 as a bilaterally absorbing element, i.e., x0=0x=0,

  3. the hypermultiplication “” is distributive with respect to the hyperoperation “+”,

  4. for all x,yR, we have xy=xy=xy.

An additive-multiplicative hyperring R is said to be commutative if R is a commutative semihypergroup. and R is called a hyperring with multiplicative identity if there exists eR such that xe=x=ex for every xR.

We close this section with the following definition of the ideal in a additive-multiplicative hyperring.

Definition 4.8 A non-empty subset A of an additive-multiplicative hyperring R is a left (right) hyperideal if,

  1. for all a,bA, then abA,

  2. for all aA, rR, then raA (arA).

4.2 Hypervector spaces over hyperfields

We give some properties related to the hypervector space as it is done by Sanjay Roy and Samanta [23] and all these will allow us to characterize linear codes over a Krasner hyperfield.

From now on, and for the rest of this section, by F we mean a Krasner hyperfield.

Definition 4.9. [23] Let F be a Krasner hyperfield. A commutative hypergroup VV together with a map :F×VV, is called a hypervector space over F if for any a,bF and x,yV, the following conditions hold:

  1. axVy=axVay (right distributive law),

  2. aVbx=axVbx (left distributive law),

  3. abx=abx (associative law),

  4. ax=ax=ax,

  5. x=1x.

Let us give that trivial example of a hypervector space.

Example 4.10. Let nN, Fn is a hypervector space over F where the composition of elements are as follows:

xy=zFnzixiyii=1n and ax=ax1ax2axn for any x,yFn and aF.

Definition 4.11. [23] Let V1 be a hypervector space over F. A subset AV is called a subhypervector space of V if:

  1. A0,

  2. for all x,yA, then xyA,

  3. for all aF, for all xA, then axA.

Definition 4.12. [23] Let S be a subset of a hypervector space V over F. S is said to be linearly independent if for every x1,x2,,xn in S and for every a1,a2,,an in F, (nN\01) such that 0a1x1+a2x2++anxn implies that a1=a2==an=0.

If S is not linearly independent, then we said that S is linearly dependent.

If S is a nonempty subset of V, then the smallest subhypervector space of V containing S is the set define by S=i=1naixixiSaiFnN\01lS, (where lS=axaFxS).

Definition 4.13. [23] Let V be a hypervector space over F. A vector xV is said to be a linear combination of the vectors x1,x2,,xnV if there exist a1,a2,,anF such that xa1x1+a2x2++anxn in the hypervector spaces, the notion of basis exists and he have the following definition.

Definition 4.14. [23] Let V be a hypervector space over F and B be a subset of V. The set B is said to be a basis for V if,

  1. S is linearly independent,

  2. every element of V can be expressed as a finite linear combination of elements from S.

4.3 Polynomial hyperring

We assume that F is such that for all a,bF, ab=ab=ab.

Let denote by Fx the set of all polynomials in the variable x over F. Let the polynomials fx=i=0naixi and gx=i=0mbixi in Fx.

Let us define the set PFx={k=0nAkxk; where AkPF, nN}, the hypersum and hypermultiplication of fx and gx are defined as follows:

¯:Fx×FxPFxE1
fxgxf¯gx=a0b0+a1b1x++aMbMxM,E2
whereM=maxnm.E3
¯:Fx×FxPFxE4
fxgxf¯gx=k=0m+nl+j=kalbjxk,ifdegf1anddegg1E5

The following remark is from Jančic-Rašović [24].

Remark 4.15. The algebraic hyperstructure Fx¯¯ is an additive-multiplication hyperring.

4.4 Linear codes and cyclic codes over finite hyperfields

In this section we shall define and discuss about the concept of linear and cyclic codes over the finite Krasner hyperfield F2 from the Example 4.6. Let us recall some basics from code theory. Let C be a linear code, the Hamming distance dHxy between two vectors x,yC is defined to be the number of coordinates in which x differs from y. The minimum distance of a code C, denoted by dC, is dC=min{dHxyx,yC and xy}. In this case we can also compute for a code word xC, the integer wHx which is the number of nonzero coordinates in x also called Hamming weight of x.

We denoted by k=dimC the dimension of C and the code C is called an nkd -code which can be represented by his generator matrix [25].

Let us define linear code over F2.

Definition 4.16. A subhypervector space of the hypervector space F2n is called a linear code C of length n over F2.

The concept of dual code is a very useful in the coding theory. Let us define it on the Krasner hyperfield F2.

Definition 4.17. Let C be a linear code of length n (n2) over F2. The dual of C is also a linear code defined by CyF2n0xytxC.

The code C is self-dual if C=C.

Here is an basic example of a linear code and his dual.

Example 4.18. Let C=000,101,011,110,111 be a linear code of length 3 over F2. It’s easy to check that the dual of C is defined by C=000,111.

As in the classical case, the notion of cyclic code on hyperstructures still works with polynomials. So i that way the polynomial fx=a0+a1x1+a2x2++an1xn1 of degree at most n1 over F2 may be considered as the sequence a=a0a1a2an1 of length n in F2n. In fact, there is a correspondence between F2n and the residue class hyperring F2xxn1 [25].

ξ:F2nF2xxn1c=c0c1c2cn1c0+c1x1+c2x2++cn1xn1.

Using Theorem 3.7 in [26], the multiplication of x by any element of F2xxn1 is equivalent to applying the shift map s of the Definition?? to the corresponding element of F2n, so we use the polynomial to define cyclic code.

We are now going to define a distance relation on linear codes over the finite hyperfield F2, which will allow us to detect if there is an error in a received word.

Proposition 4.19. The mapping define by

dH:F2n×F2nNxydHxy=cardiNxiyi

is a distance on F2n, called the Hamming distance.

Proof. The proof is similar to the classical case.

The following remark will be helpful to define Hamming weight.

Remark 4.20. For an xF2n, we write x=x1xn such that x belongs now to the cartesian product PF2n. Hence we can compute wHx=cardiN0xi=dH0x.

The following map denoted by wH on the cartesian product PF2n:

wH:PF2nNa=a1ancardiN0ai.

is the Hamming weight on F2n. So for all x,yF2n, we have dHxy=wHxy.

If C is a linear code over F2, the integer number d=minwHxxC is called the minimal distance of the code C.

To characterized a linear code of length n over F2 as a subhypervector space of F2n, it is sufficient to have a basis of that linear code. This basis can often be represented by a k×n-matrix over F2 (where k is the dimension of the code).

We denoted by MF2 be the set of all matrices over F2.

Definition 4.21. Let C be a linear code over F2. We called a generator matrix of C any matrix from MF2 where the rows form a basis of the code C.

Proposition 4.22. Let B˩Mk×nF2 be a generating matrix of the linear code C over F2, then C=caB˩aF2k.

Proof. Let C be a nk-linear code over F2 and B˩ a generating matrix of C. Then the rows of B˩Mk×nF2 form a basis of C. So C consists of all linear combinations of the rows of B˩, therefore C=caB˩aF2k. .

It is know that the dual code C of the linear code C over F2 is also linear, so C has a generating matrix called a parity check matrix.

Here and until the end of this paper, we will denoted by B˩ the generating matrix and by H˩ the parity check matrix of the linear code C over F2.

Example 4.23. Let B˩=101011 be a generating matrix of the linear code C from Example 4.18. Then the parity check matrix of C is H˩=111.

Theorem 4.24. Let C be a linear code of length n (n2) and dimension k over F2. Then H˩Mnk×nF2 and 0B˩H˩t. (It should be noted that H˩t means the transpose of H˩).

Proof. Let the generating matrix and the parity check matrix be denoted respectively by B˩=g1gk and H˩=h1hnk, where giF2n and hjF2n (for i=1k and j=1nk).

Then, B˩H˩t=g1h1tg1h2tg1hnktg2h1tg2h2tg2hnktgkh1tgkh2tgkhnkt. Thus, by the definition of C, 0B˩H˩t.

We now give some examples of linear codes over F2 and we make some comparison between the linear codes over the finite field with two elements F2 and the linear code over the Krasner hyperfield F2.

Example 4.25. Let F23 be a hypervector space over F2 and C be a subhypervector space of F23, with dimensional k=2. Then C is a linear code of length n=3 and dimension k=2 over F2.

  1. 1. Let B1=010101 be a generating matrix of the linear code C1=000,010,101,111 over F2. B1 is also a generating matrix of a linear code C2=000,010,101,111 of length 3 and dimension 2 over the finite field F2. These two codes C1 and C2 have the same parameters and cardC1=cardC2.

  2. 2. Let B2=110101 be another generating matrix of the linear code C over F2. B2 is also a generating matrix of a linear code C2 of length 3 and dimension 2 over the finite field F2.

Here we have that C1=000,110,101,011,111, C2=000,110,101,011, so these two codes have the same parameters but cardC1>cardC2.

  1. 3. Let Bmin=IdkIdnk0 (where Idk is the k×k-identity matrix).

Bmin is a generating matrix of a linear code Cmin of length n and dimension k over F2 (with nkk). The linear code Cmin over F2 generated by Bmin has the minimal number of code words, cardCmin=2k.

  1. 4. Let Bmax=Idk1nk (where Idk is the identity matrix and 1nk is the matrix such that every element is equal to 1).

Bmax is a generating matrix of a hyperlinear code Cmax of length n and dimension k>2 over F2. The linear code Cmax over F2 generated by Gmax has the maximal number of code words, cardCmax=2nk+i=2k1ki+k+1.

This remark is deduce from the previous example.

Remark 4.26. There exists a finite hyperfield such that for any other finite field of the same cardinality, the linear codes over the hyperfield are always better than the classical linear code over the finite field. (i.e., they have more code words).

In classical coding theory, one of the most important problems mentioned by MacWilliams and Sloane in their book The Theory of Error-Correcting Codes [27] is to find a code with a large number of words knowing the parameters (length, dimension and minimal distance). So the hyperstructure theory may help to increase the number of code words. That is the subject of the next theorem.

Theorem 4.27. Let C be a linear code of length n and dimension k over F2. If M is the cardinality of C, then 2kM2nk+k+1,ifk2;2nk+i=2k1ki+k+1,ifk>2..

Proof. Since a generating matrix contains a basis of the linear code C as rows, it is sufficient to give a way how to construct a generator matrix for the code where the cardinality is maximal.

If k2, this is trivial.

If k>2, then we choose a generator matrix such that:

1. in the first k columns no 1 is repeated. (this forces that every code word belongs to only one linear combination).

2. not any sum of elements in one column is equal to zero.

3. all the elements of the nk last columns are equal to 1. (because we need every combination has the maximal number of code words)

Therefore, the maximal number of code words is 2nk+i=2k1ki+k+1. We deduce from the Theorem 4.27 what is follow, which mean that a linear code over the hyperfield F2 satisfies the Singleton bound.

Corollary 4.28. Let C be a linear code of length n and dimension k over F2, and C be a linear code of length n and dimension k over the finite field F2. Then ddnk+1 (where d is the minimal distance of C and d is the minimal distance of C).

The following next propositions give some characterization of the linear codes over F2 using their generating matrix and their parity check matrix.

Proposition 4.29. Let C be a linear code of length n and dimension k over F2, then cC if and only if 0cH˩t.

Proof. ): Let cC and H˩=h1hnk be the parity check matrix of the code C. Then cH˩t=ch1tch2tchnkt, thus by definition of C, 0cH˩t.

) Assume that 0cH˩t, then c belongs either to B˩, or to a linear combination of rows of B˩. Therefore cC.

Proposition 4.30. Let C be a linear code of length n over F2, then the double dual of C is equals to C, that is C=C.

Proof. Using Proposition 4.3 in [26], C is a linear code of length n over F2, so it is sufficient to show that C=C. By definition we have C={aF20yat; for all yC}, so it is straightforward that CC. Now, let aC. Let H˩=h1hnk be the parity check matrix of the code C, then aH˩t=i=1naih1,ii=1naihnk,i

=i=1nh1,iaii=1nhnk,iai=i=1nh1,iati=1nhnk,iat.

Thus 0aH˩t by definition of C, therefore aC. We conclude the proof by using Proposition 4.29.

It is known from [26] that cyclic code in F2n has only one generating polynomial, so it is clear that this polynomial divides the polynomial xn1.

Proposition 4.31. If gx=a0+a1x++akxkF2x, is the generating polynomial for a cyclic code C over F2, then B˩=a0ak0000a0ak0000a0ak0000a0ak is the generator matrix of the cyclic code C.

Proof. Let g1=a0ak00F2n, then B˩ can also be write as B˩=g1sg1=g2s2g1=g3sk1g1=gk (where s is the shift function and sk=sss, k-successive shifts).

Since the polynomial g generates C, we have C=<gx>. Let cC, then cii=1n=cgxpx (where b0+b1x++bn1xn1=pxF2xxn1) implies that cil+jalbj if ik and ci=0 else if (i>k).

Focus on gx and px, the element c belongs to the sum b0gx+b1xgx++bn1xn1gx because this sum can also be written as e1g1+e2g2++ekgk (e=e1ekF2n), and C is a cyclic code generated by gx.

The following Proposition use same notations as in Proposition 4.31.

Proposition 4.32. [28] Let hxF2xxn1 be a polynomial such that xn1hxgx, then

  1. The linear code C over F2 can be represented as C=pxF2xxn10pxhx.

  2. hx is the generating polynomial for the linear code C.

To illustrate what is doing for cyclic codes and polynomials, we have this example.

Example 4.33. Let C be a linear code over F2 generate by the polynomial gx=1+x2F2xx31. Then the generator matrix of the code C is given by B˩=101110.

Since x311+x2̇1+x+x2, then the polynomial hx=1+x+x2 is the parity check polynomial of the code C, and the parity check matrix is given by H˩=111.

Thus C=pxF2xx31x31pẋ1+x+x2=01+x21+x1+x+x2x+x2.

Advertisement

5. Conclusions

This Chapter divides in three sections Fuzzy linear codes over Zpk, Fuzzy Zpk-linear codes and Linear codes over Krasner hyperfields just introduce some new perspectives in the field of coding theory. In the first and second section, we define and give some related properties of these on codes. We show in some example that fuzzy linear code can deal with uncertain information directly. The third section, which joint the previous sections in the sense that fuzzy fields/rings and Krasner hyperfields are non classical structures which approxim very well many real life situation, study linear codes over Krasner hyperfields as linear codes over finite fields. Many of their properties are given and the important thing that arise here is that with almost the same parameters linear codes construct on Krasner hyperfields have much code words than one construct on fields.

References

  1. 1. L.A. Zadeh, Fuzzy sets, Information and Control 8 338-353 (1965).
  2. 2. F. Marty, Sur une generalization de la notion de groupe, 8iem congres Math. Scandinaves,Stockholm, 45-49 (1934).
  3. 3. M. Krasner, A Class of Hyperrings and Hyperfields, Internat. J. Math. and Math. Sci. 6, 307-312 (1983).
  4. 4. C.E. Shannon, Communication in presence of noise, IEEE, 37, 10-21 (1949).
  5. 5. K. P. Shum, Chen De Gang, Some note on the theory of fuzzy code, Electronic BUSEFAL-81, Polytech.univ-savoie, France 132-136 (2000).
  6. 6. L. O. Hall and G. Diall, On fuzzy code for asymmetric and unidirectional errors, Fuzzy sets and systems 36, 365-373 (1990).
  7. 7. P.A. Von Kaenel, Fuzzy codes and distance properties, Fuzzy sets and systems 8, 199-204 (1982).
  8. 8. F. Galand, Construction de codes Zpk-linéaires de bonne distance minimale et schémas de dissimulation fondés sur les codes de recouvrement, Ph.D Thesis, Université de Caen, (2004).
  9. 9. M. Maschinchi and M.M. Zahedi, On L-fuzzy primary submodules, Fuzzy Sets and Systems 49, 231-236 (1992).
  10. 10. C.V. Negoita and D.A. Ralescu, Applications of Fuzzy Sets and System Analysis, (Birkhous, Basel) (1975).
  11. 11. R. Biswas, Fuzzy fields and fuzzy linear space redefined, Fuzzy Sets and Systems 33, 257-259 (1989).
  12. 12. S. Nanda, Fuzzy fields and fuzzy linear space, Fuzzy Sets and Systems 19, 89-94 (1986).
  13. 13. M. Kondo, Wieslaw A. Dubek, On transfer principle in fuzzy Theory, Mathware and soft computing 12, 41-55 (2005).
  14. 14. C. Carlet, Z2k-linear codes, IEEE Transactions on Informations Theory 44, 1543-1547 (1998).
  15. 15. S. Atamewoue Tsafack , S. Ndjeya , L. Strüngmann and C. Lele, Fuzzy Linear Codes, Fuzzy Information and Engineering, https://doi.org/10.1080/16168658.2019.1706959 (2020).
  16. 16. L.A. Zadeh, The concept of a linguistic variable and its application to approximate reasoning I, II, III, Information Sciences 8-9, 199-257, 301-357, 43-80 (1975).
  17. 17. A.M. Kerdock, A class of low-rate nonlinear codes, Information and Control 20 (1972).
  18. 18. R. Hammons, P.V. Kumar, A.R. Calderbank, N.J.A. Sloane et P. Solé, Kerdock, Preparata, Goethals and other codes are linear over Z4, IEEE Transactions on Information Theory 40, 301-319 (1994).
  19. 19. I. Perfilieva, Fuzzy function: Theoretical and practical point of view. Atlantis Press 480-486 (2011).
  20. 20. R. Ameri and O.R. Dehghan, On Dimension of Hypervector Spaces, European Journal of Pure and Applied Mathematics 1, 32-50 (2008).
  21. 21. P. Corsini and V. Leoreanu, Applications of Hyperstructure Theory, Kluwer Academical Publications, Dordrecht, (2003).
  22. 22. B. Davvaz and V. Leoreanu-Fotea, Hyperring Theory and applications, International Academic Press, USA, (2007).
  23. 23. Sanjay Roy and T.K. Samanta, A Note on Hypervector Spaces, Discussiones MathematicaeGeneral Algebra and Applications 31, 75-99 (2011).
  24. 24. S. Jančic-Rašović, About the hyperring of polynomial, Ital. J. Pure Appl. Math. 21, 223-234 (2007).
  25. 25. F. Galand, Construction de codes Zpk-linéaires de bonne distance minimale et schémas de dissimulation fondés sur les codes de recouvrement, Ph.D Thesis, Université de Caen, (2004).
  26. 26. B. Davvaz and T. Musavi, Codes Over Hyperrings, Matematički Vesnik 68, 26-38 (2016).
  27. 27. F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, (1977).
  28. 28. S. Atamewoue Tsafack, S. Ndjeya, L. Strüngmann and C. Lele, Codes over Hyperfields, Discussioness Mathematicae Genenal Algerbra and Applcations 37, 147-160 (2017).

Written By

Surdive Atamewoue Tsafack

Reviewed: 29 March 2021 Published: 11 August 2021