Open access peer-reviewed chapter - ONLINE FIRST

Non Classical Structures and Linear Codes

By Surdive Atamewoue Tsafack

Submitted: December 5th 2020Reviewed: March 29th 2021Published: August 11th 2021

DOI: 10.5772/intechopen.97471

Downloaded: 27

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 Xbe a non-empty set, let Iand Jbe two fuzzy subsets in X, then:

  • IJx=minIxJx, IJx=maxIxJx,

  • I=Jif and only if Ix=Jx, IJif and only if IxJx,

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

These for all x,y,zX.

Let denoted by Mthe Zpk-module Zpkn, where pis 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 Fof a Zpk-module Msuch that for all x,yMand rZpk, we have:

  • Fx+yminFxFy.

  • FrxFx.

Definition 2.3.Let Fbe 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=xMFxtand Ft¯=xMFxtrespectively.

Proposition 2.4.Fis a fuzzy submodule of anZpk-moduleMif and only if for allα,βZpk;x,yM, we haveFαx+βyminFxFy.

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

Definition 2.5.We called a fuzzy ideal ofZpk, a fuzzy subsetIof a ringZpksuch that for eachx,yZpk;

  • IxyminIxIy.

  • IxymaxIxIy.

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

Definition 2.7.Let RGa ring group which is the group algebra of <x>on the ring Zpk(where xis an invertible element of Zpk). A fuzzy subset Iof RGis 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.Ais a fuzzy ideal of RG if and only if for allt01, ifAt, thenAtis 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 nover Zpk. (with na 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 Zpkall 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 Cpkand Cpktwo linear codes over Zpkof generating matrix Gand Grespectively. The codes Cpkand Cpkare 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 Cpkbe a linear code of length nover Zpk, the dual of the code Cpkthat we note Cpkis the submodule of Zpkndefine by; Cpk={afor all bCpk,a.b=0}. where “” is the natural inner product on the submodule Zpkn.

In a linear code Cpkof length nover Zpk, if for all a0an1Cpk, then sa0an1Cpk(where sis 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=Zpknbe a Zpk-module. The fuzzy submodule Fof Mis called fuzzy linear code of length nover Zpk.

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

Proposition 2.14.LetAbe a fuzzy set onZpkn.

Ais a fuzzy linear code of length nover Zpkif and only if for any t01, if At, then Atis a linear code of length nover Zpk.

Corollary 2.15.LetAbe a fuzzy set onZpkn.

Ais a fuzzy linear code of length nover Zpkif and only if the characteristic function of any upper t-level cut Atfor t01is a fuzzy linear code of length nover Zpk.

Example 2.16.Consider a fuzzy subsetFonZ4as follows:

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

ThenFis a fuzzy submodule onZ4-moduleZ4, henceFis a fuzzy linear code overZ4.

Remark 2.17.Let Fbe a fuzzy linear code of length nover Zpk, since Zpknis a finite set, then ImF=FxxZpknis finite. Let ImFis set as: t1>t2>>tm(where ti01) that is ImFhave melements.

Since Ftiis a linear code over Zpk, let Gtihis generator matrix, Fcan be determined by mmatrixes Gt1, Gt2, , Gtmas 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 F1and Fu2be two fuzzy submodules on module Zpknover the ring Zpk. We said that F1and F2are orthogonal if ImF2=1ααImF1and for all t01, F21t=F1t={yZpkn<x,y>=0,for all xF1t}. Where <,>is the standard inner product on Zpkn.

Noted that F1F2means F1and F2are orthogonal. We what is follow as an example.

Example 2.19.Consider the two fuzzy submodulesF1andF2onZ4defined as follows:

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

We easily observe that:

F112=0and F212=Z4,

F114=Z4and F134=0,

F113=02and F123=02.

Thus F1F2.

Remark 2.20.Let F1be a fuzzy submodule on module Zpknsuch that xZpkn, F1x=γ(with γ01), then it does not exists a fuzzy set Fon Zpknsuch 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.LetF1be a fuzzy submodule on a finite moduleZpkn. IfImF1have more that one element and for allςImF1there existϵImF1such thatAς=Aϵ, then there always exists a fuzzy submoduleF2onZpknsuch thatF1F2.

Proof. Let F1be a fuzzy submodule on Zpkn. Assume that ImF1=m>1and for any ςImAthere exist ϵImF1such 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 Fas follow:

F:Zpkn01, x1tmi+1, if xMi.

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

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

Then by taken F2=Fwe obtain the need fuzzy submodule.

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

Theorem 2.22.LetF1, F2andF3be three fuzzy submodules on moduleZpkn, such thatF1F2andF1F3, thenF2=F3.

Proof. Consider that F1F2and F1F13.

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

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

Corollary 2.23.The orthogonal of a fuzzy set onZpknis a fuzzy submodule onZpkn.

The orthogonality is an indempotent operator, in fact if Fbe a fuzzy submodule on Zpknthen F=F1.

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

Definition 2.24.Let F1and F2be two fuzzy linear codes over Zpk. F1and F2are said to be equivalent if for all t01, the linear codes F1tand F2tare equivalent.

Example 2.25.LetCG1andCG2be two equivalent linear codes of lengthnoverZpk.

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=CG1and F21=CG2,

F10=Zpknand F20=Zpkn.

Remark 2.26.Two equivalent fuzzy linear codes over Zpkhave 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=Z22and Rn=Z23, that means that k=2and n=3. Let CR3be a linear code over R, in the classical case, when we send a codeword a=101Cthrough a communication channel, the signal receive can be read as a=0.98,0.03,0.49and modulate to a=100. Thus to know if abelong to the code C, we use syndrome calculation [14]. Since the modulation have gave a wrong word, we can consider that ahave 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 Cbe a linear code over Z23. To each aC, we find t01such that testimate the degree of which the element of R3, obtain from athrough the transmission channel belong to the code C. Thus in Z23the information that we handle are certain, whereas in R3there are uncertain. When we associate to all elements of Z23the 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 Cjust 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.LetZ23=000,001,010,100,110,101,011,111andC=000,001,110,111be a linear code overZ2.

Assume that after the transmission we obtain respectively 0000.01,011.01,101.001,1,0.999. Let F:Z2301such 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 t01such 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 nand pare coprime.

Definition 2.28.A fuzzy module Fon the module Zpknis called a fuzzy cyclic code of length nover Zpkif for all a0a1an1Zpkn, then Fan1a0an2Fa0a1an1.

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

Proposition 2.29.[15] A fuzzy submoduleFon onZpknis a fuzzy cyclic code if and only if for all.

a0a1an1Zpkn, we have Fa0a1an1=Fan1a0an2==

Fa1a2an1a0.

Proposition 2.30.Fis a fuzzy cyclic code of lengthnoverZpkif and only if for allt01, ifFt, thenFtis a ideal of the factor ringZpkXXn1.

Proof. Assume that Fis a fuzzy cyclic code over Zpkand t01such that Ft. Then Ftis 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 Zpkonto the ideals of the factor ring ZpkXXn1. Therefore, t01, Ftis a ideal of ZpkXXn1.

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

Since Zpkis a finite ring, then ImF=Fx01xZpknis also finite. Assume that ImF=t1>t2>>tm, then Ft1Ft2Ftm1Atm=Zpkn.

Let gikXZpkXthe generator polynomial of Fti, note that gikXis the Hensel lifting of order kof some polynomial giXZpXwhich divide Xn1, the cyclic code <gikX>ZpkXXn1is called the lifted codeof the cyclic code <giX>ZpXXn1[8].

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

Theorem 2.31.LetG=g1kXg2kXgmkXbe a set of polynomial inZpkX, such thatgiXdivideXn1, i=1,,m. Ifgi+1kXgikXfori=1,2,,m1and<gmkX>=Zpkn, then the setGcan determined a fuzzy cyclic codeFand<gikX>i=1mis the family of upper level cut cyclic subcodes ofF.

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

3. Fuzzy Zpk-linear code

In the previous section, we study define and fuzzy linear codes over the ring Zpkin 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 ϕ:Z22Z22the 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, FZ22the set of all the fuzzy subset on Z22and Z22respectively. 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.IfFis a fuzzy linear code overZ22andϕthe Gray map, thenϕ̂Fis no always a fuzzy linear code over the fieldZ2.

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 Cis a linear code of length nover Z4, then C=ψCis a nonlinear code of length 2nover Z2in generally [18]. In that way we construct a fuzzy Kerdock code in the following example.

Example 3.4.LetG=10002111010012130010132100011132be a generating matrix for a linear codeCof length8overZ4. Then his image under the Gray mapϕgive a Kerdock codeC.

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

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

where E={yZ216y=ϕxand xC}.

Noted that as Eis not a linear code over Z2, then ϕ̂Fuis a fuzzy Z2-linear code but not a fuzzy linear code over Z2.

ϕ̂Fis 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×Z22by Rϕxy=1,ify=ψx;0,otherwise.It is easy to see [19] that ϕ̂Fy=supFxy=ϕxcan 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 Φ:ZpkZppk1cannot give more than one image for one element.

  2. Let F1FZppk1such that F1y=t0for any yZppk1. There does not exist a fuzzy subset FFZpksuch that Φ̂F=F1.

Thus Φ̂is not a bijection map.

3.2 Fuzzy Zpk-linear code

In the following, we will note Φ̂the map on FZpknonto FZpn.pk1which spreads the fuzzy generalized Gray map.

Let define fuzzy Zpk-linear code.

Definition 3.7.A fuzzy code Fuover Zpis 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 Fuis 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.

Fis a fuzzy linear code of length 6 over Z2.

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

Fis a fuzzy linear code of length 3 over Z4.

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

Using crisp case technic we prove he following Proposition.

Proposition 3.10.LetFube a fuzzyZpk-linear code, thenFuis no always a fuzzy linear code over the fieldZp.

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. LetF:Zpkn01be a linear code such thatFhave three uppert-level cutFt3Ft2Ft1. LetFt3=ΦFt3, Ft2=ΦFt2andFt1=ΦFt1, we haveFt3=ΦFt3Ft2=ΦFt2Ft1=ΦFt1. We constructF=Φ̂Fas 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=02and F14=Z4.

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

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

We obtain the same code Fand ϕ̂F.

Proposition 3.12.[15] If for allt01, Ft=ΦFt(whenFt) is a linear code overZp, then this two constructions of the fuzzyZp-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.

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 Hbe a non-empty set and PHbe the set of all non-empty subsets of H. Then, a map :H×HPH, where h1h2h1h2His called a hyperoperation and the couple His called a hypergroupoid.

For all non-empty subsets Aand Bof Hand hH, we define AB=aA,bBab, Ah=Ahand hB=hB.

Definition 4.1.A canonical hypergroup Ris 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 0Rsuch that 0x=xfor every xR.

  4. For every xRthere exists a unique element x(an opposite of xwith respect to hyperoperation “”) in Rsuch that 0xx,

  5. For any x,y,zR, zxyimplies yxzand xzy.

Remark 4.2.Note that, in the classical group R+, the concept of opposite of xRis 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. Ris a canonical hypergroup with 0as additive identity,

  2. Ris a semigroup having 0as 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 Ris a commutative semigroup (with unit element) and such is denoted R,0,1.

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

This Example is from Krasner.

Example 4.5.[?] Consider a fieldF+and a subgroupGofF\0. TakeH=F/G=aGaFwith the hyperoperation and the multiplication given by:

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

Then His a Krasner hyperfield.

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

Example 4.6.LetF2=01be the finite set with two elements. ThenF2becomes a Krasner hyperfield with the following hyperoperation “” and binary operation “”.

01
001
1101

and

01
000
101

Let Rbe a hyperring, Aand Bbe a non-empty subset of R. Then, Ais said to be a subhyperring of Rif (A,,) is itself a hyperring. A subhyperring Aof a hyperring Ris a left (right) hyperideal of Rif raA(arA) for all rR, aA. Also, Ais called a hyperideal if Ais both a left and a right hyperideal. We define ABby AB={xxabfor some aA,bB}and the product ABis defined by AB={xxi=1naibi,with aiA,biB,nN}. If Aand Bare hyperideals of R, then ABand ABare 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. Ris a canonical hypergroup with 0as additive identity,

  2. Ris a semihypergroup having 0as 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 Ris said to be commutative if Ris a commutative semihypergroup. and Ris called a hyperring with multiplicative identity if there exists eRsuch that xe=x=exfor every xR.

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

Definition 4.8A non-empty subset Aof an additive-multiplicative hyperring Ris 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 Fwe mean a Krasner hyperfield.

Definition 4.9.[23] Let Fbe a Krasner hyperfield. A commutative hypergroup VVtogether with a map :F×VV, is called a hypervector space over Fif for any a,bFand 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.LetnN, Fnis a hypervector space overFwhere the composition of elements are as follows:

xy=zFnzixiyii=1nand ax=ax1ax2axnfor any x,yFnand aF.

Definition 4.11.[23] Let V1be a hypervector space over F. A subset AVis called a subhypervector space of Vif:

  1. A0,

  2. for all x,yA, then xyA,

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

Definition 4.12.[23] Let Sbe a subset of a hypervector space Vover F. Sis said to be linearly independent if for every x1,x2,,xnin Sand for every a1,a2,,anin F, (nN\01) such that 0a1x1+a2x2++anxnimplies that a1=a2==an=0.

If Sis not linearly independent, then we said that Sis linearly dependent.

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

Definition 4.13.[23] Let Vbe a hypervector space over F. A vector xVis said to be a linear combination of the vectors x1,x2,,xnVif there exist a1,a2,,anFsuch that xa1x1+a2x2++anxnin the hypervector spaces, the notion of basis exists and he have the following definition.

Definition 4.14.[23] LetVbe a hypervector space overFandBbe a subset ofV. The setBis said to be a basis forVif,

  1. Sis linearly independent,

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

4.3 Polynomial hyperring

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

Let denote by Fxthe set of all polynomials in the variable xover F. Let the polynomials fx=i=0naixiand gx=i=0mbixiin Fx.

Let us define the set PFx={k=0nAkxk;where AkPF, nN}, the hypersum and hypermultiplication of fxand gxare 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 F2from the Example 4.6. Let us recall some basics from code theory. Let Cbe a linear code, the Hamming distance dHxybetween two vectors x,yCis defined to be the number of coordinates in which xdiffers from y. The minimum distance of a code C, denoted by dC, is dC=min{dHxyx,yCand xy}. In this case we can also compute for a code word xC, the integer wHxwhich is the number of nonzero coordinates in xalso called Hamming weight of x.

We denoted by k=dimCthe dimension of Cand the code Cis 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 F2nis called a linear code Cof length nover 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 Cbe a linear code of length n(n2) over F2. The dual of Cis also a linear code defined by CyF2n0xytxC.

The code Cis self-dual if C=C.

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

Example 4.18.LetC=000,101,011,110,111be a linear code of length3overF2. It’s easy to check that the dual ofCis defined byC=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++an1xn1of degree at most n1over F2may be considered as the sequence a=a0a1a2an1of length nin F2n. In fact, there is a correspondence between F2nand the residue class hyperring F2xxn1[25].

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

Using Theorem 3.7 in [26], the multiplication of xby any element of F2xxn1is equivalent to applying the shift map sof 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=x1xnsuch that xbelongs now to the cartesian product PF2n. Hence we can compute wHx=cardiN0xi=dH0x.

The following map denoted by wHon the cartesian product PF2n:

wH:PF2nNa=a1ancardiN0ai.

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

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

To characterized a linear code of length nover F2as 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 kis the dimension of the code).

We denoted by MF2be the set of all matrices over F2.

Definition 4.21.Let Cbe a linear code over F2. We called a generator matrix of Cany matrix from MF2where the rows form a basis of the code C.

Proposition 4.22.LetB˩Mk×nF2be a generating matrix of the linear codeCoverF2, thenC=caB˩aF2k.

Proof.Let Cbe a nk-linear code over F2and B˩a generating matrix of C. Then the rows of B˩Mk×nF2form a basis of C. So Cconsists of all linear combinations of the rows of B˩, therefore C=caB˩aF2k. .

It is know that the dual code Cof the linear code Cover F2is also linear, so Chas 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 Cover F2.

Example 4.23.LetB˩=101011be a generating matrix of the linear codeCfrom Example 4.18. Then the parity check matrix ofCisH˩=111.

Theorem 4.24.LetCbe a linear code of lengthn(n2) and dimensionkoverF2. ThenH˩Mnk×nF2and0B˩H˩t. (It should be noted thatH˩tmeans the transpose ofH˩).

Proof.Let the generating matrix and the parity check matrix be denoted respectively by B˩=g1gkand H˩=h1hnk, where giF2nand hjF2n(for i=1kand 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 F2and we make some comparison between the linear codes over the finite field with two elements F2and the linear code over the Krasner hyperfield F2.

Example 4.25.LetF23be a hypervector space overF2andCbe a subhypervector space ofF23, with dimensionalk=2. ThenCis a linear code of lengthn=3and dimensionk=2overF2.

  1. LetB1=010101be a generating matrix of the linear codeC1=000,010,101,111overF2. B1is also a generating matrix of a linear codeC2=000,010,101,111of length 3 and dimension 2 over the finite fieldF2. These two codesC1andC2have the same parameters andcardC1=cardC2.

  2. LetB2=110101be another generating matrix of the linear codeCoverF2. B2is also a generating matrix of a linear codeC2of length 3 and dimension 2 over the finite fieldF2.

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. LetBmin=IdkIdnk0(whereIdkis thek×k-identity matrix).

Bminis a generating matrix of a linear code Cminof length nand dimension kover F2(with nkk). The linear code Cminover F2generated by Bminhas the minimal number of code words, cardCmin=2k.

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

Bmaxis a generating matrix of a hyperlinear code Cmaxof length nand dimension k>2over F2. The linear code Cmaxover F2generated by Gmaxhas 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.LetCbe a linear code of lengthnand dimensionkoverF2. IfMis the cardinality ofC, then2kM2nk+k+1,ifk2;2nk+i=2k1ki+k+1,ifk>2..

Proof.Since a generating matrix contains a basis of the linear code Cas 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 kcolumns no 1is 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 nklast 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 F2satisfies the Singleton bound.

Corollary 4.28.LetCbe a linear code of lengthnand dimensionkoverF2, andCbe a linear code of lengthnand dimensionkover the finite fieldF2. Thenddnk+1(wheredis the minimal distance ofCanddis the minimal distance ofC).

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

Proposition 4.29.LetCbe a linear code of lengthnand dimensionkoverF2, thencCif and only if0cH˩t.

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

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

Proposition 4.30.LetCbe a linear code of lengthnoverF2, then the double dual ofCis equals toC, that isC=C.

Proof.Using Proposition 4.3 in [26], Cis a linear code of length nover 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˩=h1hnkbe 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˩tby definition of C, therefore aC. We conclude the proof by using Proposition 4.29.

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

Proposition 4.31.Ifgx=a0+a1x++akxkF2x, is the generating polynomial for a cyclic codeCoverF2, thenB˩=a0ak0000a0ak0000a0ak0000a0akis the generator matrix of the cyclic codeC.

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

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

Focus on gxand px, the element cbelongs to the sum b0gx+b1xgx++bn1xn1gxbecause this sum can also be written as e1g1+e2g2++ekgk(e=e1ekF2n), and Cis a cyclic code generated by gx.

The following Proposition use same notations as in Proposition 4.31.

Proposition 4.32.[28] LethxF2xxn1be a polynomial such thatxn1hxgx, then

  1. The linear codeCoverF2can be represented asC=pxF2xxn10pxhx.

  2. hxis the generating polynomial for the linear codeC.

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

Example 4.33.LetCbe a linear code overF2generate by the polynomialgx=1+x2F2xx31. Then the generator matrix of the codeCis given byB˩=101110.

Since x311+x2̇1+x+x2, then the polynomial hx=1+x+x2is 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.

5. Conclusions

This Chapter divides in three sections Fuzzy linear codes overZpk, FuzzyZpk-linear codesand Linear codes over Krasner hyperfieldsjust 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.

DOWNLOAD FOR FREE

chapter PDF

© 2021 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Surdive Atamewoue Tsafack (August 11th 2021). Non Classical Structures and Linear Codes [Online First], IntechOpen, DOI: 10.5772/intechopen.97471. Available from:

chapter statistics

27total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us