Algebraic decoding method and decoder for (n,n(n-1),n-1)-PGC in communication modulation system

Abstract

The disclosure discloses an algebraic decoding method and a decoder for a (n, n(n−1), n−1) permutation group code in a communication modulation system. The basic principle of the decoding method is: assuming that two code elements p(r.sub.1)=s.sub.1 and p(r.sub.2)=s.sub.2 can be correctly detected in a received real vector with a length of n, including their element values s.sub.1, s.sub.2 and position indices r.sub.1, r.sub.2 in the vector, an intermediate parameter w is determined by solving an equation (r.sub.1−r.sub.2)w=(s.sub.1−s.sub.2)(mod n); and each code element is calculated by w according to p(i)=(s.sub.1+(n−r.sub.1+i)w)(mod n), i=1, 2, . . . , n. The decoder is mainly composed of multiple n-dimensional registers, a w calculator, n code element calculators, and a code element buffer. In the disclosure, in a case where a receiver only correctly detects two code elements in a transmitted codeword with a length of n, the codeword can be correctly decoded by using the received information of the two code elements.

Claims

1. An algebraic decoding method for a (n, n(n−1), n−1) permutation group code in a communication modulation system, wherein when n is a prime number, the (n, n(n−1), n−1) permutation group code contains n(n−1) permutation codewords, each of the permutation codewords contains n code elements, and a minimum Hamming distance between any two of the permutation codewords is n−1, comprising: i) determining an intermediate parameter w: let w∈Z.sub.n be obtained by solving an expression (r.sub.1−r.sub.2)w=(s.sub.1−s.sub.2)(mod n), wherein (mod n) represents a modulo n operation; let p(r.sub.1)=s.sub.1 and p(r.sub.2)=s.sub.2 be two of the code elements correctly detected in a real signal vector received from a channel, wherein s.sub.1, s.sub.2∈Z.sub.n are respectively element values of the code elements p(r.sub.1) and p(r.sub.2), r.sub.1, r.sub.2∈Z.sub.n are respectively position indices of the code elements p(r.sub.1) and p(r.sub.2), and Z.sub.n is a positive integer finite domain represented by Z.sub.n={1, 2, . . . , n}; and both the code elements p(r.sub.1) and p(r.sub.2) are elements in a permutation codeword p with a code length of n; ii) calculating respective code elements in the permutation codeword p by using the intermediate parameter w determined in i) and the detected parameters r.sub.1 and s.sub.1 according to an expression p(i)=(s.sub.1+(n−r.sub.1+i)w)(mod n), wherein p(i) represents an element value of a code element at a position index i, and i=1, 2, . . . , n; and iii) constructing a vector with a length of n by arranging the n code elements calculated in ii) in an order of i=1, 2, . . . , n, to obtain a decoded codeword p=[p(1)p(2) . . . p(n−1)p(n)].

2. A decoder for a (n, n(n−1), n−1) permutation group code in a communication modulation system, comprising a plurality of independent n-dimensional registers, an intermediate parameter w calculator, n single-code-element calculators operating in parallel, and a n-dimensional buffer for n code elements, wherein the plurality of independent n-dimensional registers are respectively configured to store parameters r.sub.1, r.sub.2, s.sub.1, s.sub.2, n and a code element position index i; two code elements p(r.sub.1)=s.sub.1 and p(r.sub.2)=s.sub.2 are correctly detected in a real vector received from a channel, wherein s.sub.1, s.sub.2∈Z.sub.n are respectively element values of the code elements p(r.sub.1) and p(r.sub.2), r.sub.1, r.sub.2∈Z.sub.n are respectively position indices of the code elements p(r.sub.1) and p(r.sub.2), and Z.sub.n is a positive integer finite domain represented by Z.sub.n={1, 2, . . . , n}; both the code elements p(r.sub.1) and p(r.sub.2) are elements in a permutation codeword p with a code length of n; the intermediate parameter w calculator is configured to calculate an intermediate parameter w; let w∈Z.sub.n be obtained by solving an expression (r.sub.1−r.sub.2)w=(s.sub.1−s.sub.2)(mod n), wherein (mod n) represents a modulo n operation; the intermediate parameter w calculator is implemented by a calculator with a divider, or is implemented by a calculator with carry adders and a counter according to a method for calculating the intermediate parameter w in a flowchart; the n single-code-element calculators are configured to operate in parallel to simultaneously calculate n code elements in the permutation codeword p by using the intermediate parameter w and the detected parameters r.sub.1 and s.sub.1 according to an expression p(i)=(s.sub.1+(n−r.sub.1+i)w)(mod n), wherein p(i) represents an element value of a code element at a position index i, i=1, 2, . . . , n, and a i-th single-code-element calculator is configured to calculate p(i); each of the n single-code-element calculators is implemented by a calculator with a multiplier, or a calculator with an accumulator and a counter; and the n-dimensional buffer for the n code elements are configured to store and arrange the n code elements calculated by the n single-code-element calculators in an order of i=1, 2, . . . , n to construct a vector with a length of n, thereby obtaining a decoded codeword p=[p(1)p(2) . . . p(n−1)p(n)].

3. The decoder according to claim 2, wherein when the intermediate parameter w calculator is implemented by the calculator with the divider, the intermediate parameter w calculator includes four independent n-dimensional registers, two two-input adders, a divider and a modulo n operator mod n, wherein the four independent n-dimensional registers are configured to respectively store r.sub.1, −r.sub.2, s.sub.1 and −s.sub.2; two input ends of the left one of the two input adders are respectively connected to two of the four independent n-dimensional registers storing r.sub.1 and −r.sub.2, and two input ends of the right one of the two input adders are respectively connected to two of the four independent n-dimensional registers storing s.sub.1 and −s.sub.2; a left input end of the divider is configured to receive an output (r.sub.1−r.sub.2) of the left adder, a right input end of the divider is configured to receive an output (s.sub.1−s.sub.2) of the right adder, and the divider outputs a result (s.sub.1−s.sub.2)/(r.sub.1−r.sub.2); and the modulo n operator mod n is connected to an output end of the divider, and is configured to perform an modulo operation on the output result (s.sub.1−s.sub.2)/(r.sub.1−r.sub.2) of the divider and output w=(s.sub.1−s.sub.2)/(r.sub.1−r.sub.2)(mod n).

4. The decoder according to claim 3, wherein the n-dimensional buffer comprises a n-input and single-output buffer, wherein when each of the n single-code-element calculators is implemented by the calculator with the multiplier, the i-th single-code-element calculator with the multiplier includes five independent n-dimensional registers, a three-input adder, a two-input multiplier, a two-input adder and a modulo n operator, wherein i=1, 2, . . . , n, wherein the five independent n-dimensional registers are configured to respectively store i, n, −r.sub.1, w and s.sub.1; output ends of three of the five independent n-dimensional registers storing i, n and −r.sub.1 are respectively connected to three input ends of the three-input adder, and the three-input adder is configured to perform an add operation of (n−r.sub.1+i), wherein i=1, 2, . . . , n; an output end of the three-input adder is connected to one input end of the two-input multiplier, the other input end of the two-input multiplier is connected to one of the five independent n-dimensional register storing w, and the two-input multiplier is configured to perform an multiply operation of (n−r.sub.1+i)w; an output end of the two-input multiplier is connected to one input end of the two-input adder, the other input end of the two-input adder is connected to one of the five independent n-dimensional register storing s.sub.1, and the two-input adder is configured to perform an add operation of (s.sub.1+(n−r.sub.1+i)w); and an output end of the two-input adder is connected to the modulo n operator, and the modulo n operator is configured to perform an mod n operation on (s.sub.1+(n−r.sub.1+i)w), and output an i-th code element p(i) in the decode codeword.

5. The decoder according to claim 3, wherein the n-dimensional buffer comprises a n-input and single-output buffer, wherein when each of the n single-code-element calculators is implemented by the calculator with the accumulator and the counter to form a simplified single-code-element calculator, the i-th simplified single-code-element calculator includes four n-dimensional registers, a three-input adder, an enable control accumulator, a counter with an intermediate parameter w cycle-minus-one operation, a two-input adder and a modulo n operator, wherein i=1, 2, . . . , n, wherein the four n-dimensional registers of the i-th simplified single-code-element calculator are configured to respectively store i, n, −r.sub.1 and s.sub.1; output ends of three of the four n-dimensional registers of the i-th simplified single-code-element calculator storing i, n and −r.sub.1 are respectively connected to three input ends of the three-input adder to achieve an add operation of (n−r.sub.1+i); an operation result of the three-input adder is input to the enable control accumulator to achieve w times of accumulation of (n−r.sub.1+i), wherein an operation of w−1 is performed for each accumulation; when w≠0, the enable control accumulator has an enable signal E=1, so that the enable control accumulator continues to perform the accumulation operation on (n−r.sub.1+i), until w is reduced to 0, and then the enable control accumulator has an enable signal E=0, so that the accumulator stops the accumulation operation and outputs a result to one input end of the two-input adder; the other input end of the two-input adder is connected to one of the four n-dimensional register of the i-th simplified single-code-element calculator storing s.sub.1, and the two-input adder is configured to perform an add operation of (s.sub.1+(n−r.sub.1+i)w); and an output end of the two-input adder is connected to connected to the modulo n operator, and the modulo n operator is configured to perform an mod n operation on (s.sub.1+(n−r.sub.1+i)w), and output an i-th code element p (i) in the decode codeword.

6. The decoder according to claim 2, wherein the method for calculating for the intermediate parameter w in the flowchart comprises: inputting the position values r.sub.1, r.sub.2 and the element values s.sub.1, s.sub.2 of the two known code elements p(r.sub.1)=s.sub.1 and p(r.sub.2)=s.sub.2, and initializing the intermediate parameter w=1; respectively calculating u=r.sub.1−r.sub.2 and v=s.sub.1−s.sub.2; respectively determining values of u and v: if u>0, directly outputting a value of u, and if u<0, then u=n+u, outputting a value of u; similarly, if v>0, directly outputting a value of v, and if v<0, then v=n+v, outputting a value of v; and comparing the values of u and v, if u=v, then outputting w=1; if u≠v, then u=u+u, w=w+1, comparing the values of u and v again, if u≠v, continuing the operations of u=u+u and w=w+1, until u=v, then outputting w>1.

7. The decoder according to claim 6, wherein when the intermediate parameter w calculator is implemented by the calculator with carry adders and the counter to form a simplified calculator, the simplified intermediate parameter w calculator includes five n-dimensional registers, two adders with carry bit C, two single-input and double-output switches, two two-input adders, a comparator, an enable control accumulator, and an enable control counter with a feedback-plus-one operation, wherein the five n-dimensional registers are respectively store r.sub.1, −r.sub.2, s.sub.1, −s.sub.2 and n; the enable control counter with a feedback-plus-one operation has an initial value set to w=1; output ends of two of the five n-dimensional registers storing r.sub.1 and −.sub.2 are respectively connected to two input ends of the left adder with carry bit C.sub.1 to obtain a calculation result u=r.sub.1−r.sub.2, if u<0, then the carry bit C.sub.1=1, the left single-input and double-output switch is thrown to the right, u is output to the left two-input adder to achieve u=n+u, and u is output; if u>0, then the carry bit C.sub.1=0, the left single-input and double-output switch is thrown to the left, and u=r.sub.1−r.sub.2 is output; u enters the comparator through the enable control accumulator; output ends of two of the five n-dimensional registers storing s.sub.1 and −s.sub.2 are respectively connected to two input ends of the right adder with carry bit C.sub.2 to obtain a calculation result v=s.sub.1−s.sub.2, if v<0, then the carry bit C.sub.2=1, the right single-input and double-output switch is thrown to the left, v is output to the right two-input adder to achieve v=n+v, and v is output; if u>0, then the carry bit C.sub.2=0, the right single-input and double-output switch is thrown to the right, and v=s.sub.1−s.sub.2 is output; v directly enters the comparator; and the comparator compares values of u and v: if u=v, then a low-level enable signal is output, so that the enable control counter has an enable signal Ē.sub.2=1, and directly outputs w=1 without the feedback-plus-one operation; if u≠v, the enable control accumulator has an enable signal E.sub.1=1, and returns the current u to its input end for accumulating u once, if E.sub.1=0, the enable control accumulator directly outputs u to the comparator without performing the accumulation operation; if u≠v, the enable control counter has an enable signal E.sub.2=1, so that the feedback-plus-one operation is performed on the current w; as long as u≠v, the comparator, the enable control accumulator and the enable control counter repeat the above operations until u=v, resulting in Ē.sub.2=1, and E.sub.1=0, that is, the enable control accumulator does not perform the accumulation operation and the enable control counter does not perform the feedback-plus-one operation, and then a value of w is output.

8. The decoder according to claim 7, wherein the n-dimensional buffer comprises a n-input and single-output buffer, wherein when each of the n single-code-element calculators is implemented by the calculator with the multiplier, the i-th single-code-element calculator with the multiplier includes five independent n-dimensional registers, a three-input adder, a two-input multiplier, a two-input adder and a modulo n operator, wherein i=1, 2, . . . , n, wherein the five independent n-dimensional registers of the i-th single-code-element calculator with the multiplier are configured to respectively store i, n, −r.sub.1, w and s.sub.1; output ends of three of the five independent n-dimensional registers of the i-th single-code-element calculator with the multiplier storing i, n and −r.sub.1 are respectively connected to three input ends of the three-input adder, and the three-input adder is configured to perform an add operation of (n−r.sub.1+i), wherein i=1, 2, . . . , n; an output end of the three-input adder is connected to one input end of the two-input multiplier, the other input end of the two-input multiplier is connected to one of the five independent n-dimensional register of the i-th single-code-element calculator with the multiplier storing w, and the two-input multiplier is configured to perform an multiply operation of (n−r.sub.1+i)w; an output end of the two-input multiplier is connected to one input end of the two-input adder, the other input end of the two-input adder is connected to one of the five independent n-dimensional register of the i-th single-code-element calculator with the multiplier storing s.sub.1, and the two-input adder is configured to perform an add operation of (s.sub.1+(n−r.sub.1+i)w); and an output end of the two-input adder is connected to the modulo n operator, and the modulo n operator is configured to perform an mod n operation on (s.sub.1+(n−r.sub.1+i)w), and output an i-th code element p(i) in the decode codeword.

9. The decoder according to claim 7, wherein the n-dimensional buffer comprises a n-input and single-output buffer, wherein when each of the n single-code-element calculators is implemented by the calculator with the accumulator and the counter to form a simplified single-code-element calculator, the i-th simplified single-code-element calculator includes four n-dimensional registers, a three-input adder, an enable control accumulator, a counter with an intermediate parameter w cycle-minus-one operation, a two-input adder and a modulo n operator, wherein i=1, 2, . . . , n, wherein the four n-dimensional registers are configured to respectively store i, n, −r.sub.1 and s.sub.1; output ends of three of the four n-dimensional registers storing i, n and −r.sub.1 are respectively connected to three input ends of the three-input adder to achieve an add operation of (n−r.sub.1+i); an operation result of the three-input adder is input to the enable control accumulator to achieve w times of accumulation of (n−r.sub.1+i), wherein an operation of w−1 is performed for each accumulation; when w≠0, the enable control accumulator has an enable signal E=1, so that the enable control accumulator continues to perform the accumulation operation on (n−r.sub.1+i), until w is reduced to 0, and then the enable control accumulator has an enable signal E=0, so that the accumulator stops the accumulation operation and outputs a result to one input end of the two-input adder; the other input end of the two-input adder is connected to one of the four n-dimensional register storing s.sub.1, and the two-input adder is configured to perform an add operation of (s.sub.1+(n−r.sub.1+i)w); and an output end of the two-input adder is connected to connected to the modulo n operator, and the modulo n operator is configured to perform an mod n operation on (s.sub.1+(n−r.sub.1+i)w), and output an i-th code element p(i) in the decode codeword.

10. The decoder according to claim 2, wherein when each of the n single-code-element calculators is implemented by the calculator with the multiplier, the i-th single-code-element calculator with the multiplier includes five independent n-dimensional registers, a three-input adder, a two-input multiplier, a two-input adder and a modulo n operator, wherein i=1, 2, . . . , n, wherein the five independent n-dimensional registers are configured to respectively store i, n, −r.sub.1, w and s.sub.1; output ends of three of the five independent n-dimensional registers storing i, n and −r.sub.1 are respectively connected to three input ends of the three-input adder, and the three-input adder is configured to perform an add operation of (n−r.sub.1+i), wherein i=1, 2, . . . , n; an output end of the three-input adder is connected to one input end of the two-input multiplier, the other input end of the two-input multiplier is connected to one of the five independent n-dimensional register storing w, and the two-input multiplier is configured to perform an multiply operation of (n−r.sub.1+i)w; an output end of the two-input multiplier is connected to one input end of the two-input adder, the other input end of the two-input adder is connected to one of the five independent n-dimensional register storing s.sub.1, and the two-input adder is configured to perform an add operation of (s.sub.1+(n−r.sub.1+i)w); and an output end of the two-input adder is connected to the modulo n operator, and the modulo n operator is configured to perform an mod n operation on (s.sub.1+(n−r.sub.1+i)w), and output an i-th code element p(i) in the decode codeword.

11. The decoder according to claim 2, wherein when each of the n single-code-element calculators is implemented by the calculator with the accumulator and the counter to form a simplified single-code-element calculator, the i-th simplified single-code-element calculator includes four n-dimensional registers, a three-input adder, an enable control accumulator, a counter with an intermediate parameter w cycle-minus-one operation, a two-input adder and a modulo n operator, wherein i=1, 2, . . . , n, wherein the four n-dimensional registers are configured to respectively store i, n, −r.sub.1 and s.sub.1; output ends of three of the four n-dimensional registers storing i, n and −r.sub.1 are respectively connected to three input ends of the three-input adder to achieve an add operation of (n−r.sub.1+i); an operation result of the three-input adder is input to the enable control accumulator to achieve w times of accumulation of (n−r.sub.1+i), wherein an operation of w−1 is performed for each accumulation; when w≠0, the enable control accumulator has an enable signal E=1, so that the enable control accumulator continues to perform the accumulation operation on (n−r.sub.1+i), until w is reduced to 0, and then the enable control accumulator has an enable signal E=0, so that the accumulator stops the accumulation operation and outputs a result to one input end of the two-input adder; the other input end of the two-input adder is connected to one of the four n-dimensional register storing s.sub.1, and the two-input adder is configured to perform an add operation of (s.sub.1+(n−r.sub.1+i)w); and an output end of the two-input adder is connected to connected to the modulo n operator, and the modulo n operator is configured to perform an mod n operation on (s.sub.1+(n−r.sub.1+i)w), and output an i-th code element p(i) in the decode codeword.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a schematic structural diagram of a complete algebraic decoder provided by the disclosure;

(2) FIG. 2 is a schematic diagram of an intermediate parameter w calculator with a divider provided by the disclosure;

(3) FIG. 3 is a calculation flowchart of a simplified intermediate parameter w calculator provided by the disclosure;

(4) FIG. 4 is a schematic diagram of a simplified intermediate parameter w calculator provided by the disclosure;

(5) FIG. 5 is a schematic diagram of a single-code-element calculator with a multiplier provided by the disclosure;

(6) FIG. 6 is a schematic diagram of a simplified single-code-element calculator provided by the disclosure; and

(7) FIG. 7 is a schematic diagram of the architecture of a complete algebraic decoder provided by the disclosure.

DETAILED DESCRIPTION OF THE EMBODIMENTS

(8) For clear understanding of the objectives, features and advantages of the present disclosure, detailed description of the present disclosure will be given below in conjunction with accompanying drawings and specific embodiments. It should be noted that the embodiments described herein are only meant to explain the present disclosure, and not to limit the scope of the present disclosure. Furthermore, the technical features related to the embodiments of the disclosure described below can be mutually combined if they are not found to be mutually exclusive.

(9) Basic Principles

(10) Basic principles of a (n, n(n−1), n−1) permutation group code of the disclosure are described below.

(11) Assuming that code symbols can take values in a positive integer finite domain Z.sub.n={1, 2, . . . , n} or an integer finite domain Z.sub.n.sup.0={0, 1, 2, . . . , n−1}, but a description with values mainly taken in Z.sub.n={1, 2, . . . , n} is given, and the result also applies to the case where values are taken in Z.sub.n.sup.0={0, 1, 2, . . . , n−1}.

(12) Calling a set formed by all n! permutations of n elements in Z.sub.n a symmetric group S.sub.n={π.sub.1, . . . , π.sub.k, . . . , π.sub.n!}, an element in S.sub.n may be represented by a permutation vector π.sub.k=[a.sub.1 . . . a.sub.i . . . a.sub.n]. All elements of a permutation are different and represented by a.sub.1, . . . , a.sub.i, . . . , a.sub.n∈Z.sub.n. Degree (dimension, size) of a permutation is |π.sub.k|=n, and cardinality (order) of the symmetric group is |S.sub.n|=n!. Let π.sub.0=e=[a.sub.1 a.sub.2 . . . a.sub.n]=[12 . . . n] represent an identity element of the symmetric group S.sub.n. A general permutation group code is defined as a subgroup of the symmetric group s.sub.n, and expressed as (n, μ, d)−PGC, where n represents a code length, μ represents the maximum cardinality (maximum size) of the code set, and d represents a minimum Hamming distance between any two permutation codewords in the code set. For example, a (n, n(n−1), n−1) permutation group code is a group code with a code length of n, a cardinality of n(n−1) and a minimum Hamming distance of n−1.

(13) The existing published research results show that a code set P.sub.n,x.sub.i of a (n, μ, d) permutation group code (n>1) can be equivalently obtained by calculating each code by the following three methods.

(14) $\begin{array}{cc}{P}_{n,x_i}={\left\{p_1,p_2,\mathrm{.Math.},p_{n\left(n-1\right)}\right\}}_{x_i}& \mathrm{ }\left(1\right)\\ =S_n.Math.\left\{C_n\circ L_{n,x_i}\right\}=S_n.Math.{\left\{{\left\{c_i\circ l_{j,x_i}\right\}}_{i=1}^n\right\}}_{j=1}^{n-1}& \\ =S_n.Math.\{a\left(p_{1,x_i}-x_i\right)+x_i+b.Math.a\in Z_{n-1},x_i,b\in Z_n,p_{1,x_i}=& \left(2\text{-}1\right)\\ \left[1\mathrm{.Math.}n\right]\}& \\ =S_n.Math.\left\{L_{n,x_i}+b.Math.b\in Z_n\right\}& \left(2\text{-}2\right)\\ =S_n.Math.\left\{{\left(t_{\mathrm{rn}}\right)}^{n-1}{L}_{n,x_i}\right\}=S_n.Math.\left\{{\left(t_{l1}\right)}^{n-1}{L}_{n,x_i}\right\}& \left(3\right)\end{array}\hspace{1em}$
where the expression (1) represents a first method for generating the code set P.sub.n,x.sub.i, indicating that the code set P.sub.n,x.sub.i is composed by two smaller subgroups (i.e., a special cyclic subgroup C.sub.n with a cardinality of |C.sub.n|=n and a largest single fixed point subgroup L.sub.n,x.sub.i) with an operator “∘”; the expressions (2-1) and (2-2) represent a second method for generating the code set P.sub.n,x.sub.i, indicating that each permutation codeword in the code set P.sub.n,x.sub.i can be calculated by affine transformation f.sub.a,b(p.sub.1,x.sub.i)=a(p.sub.1,x.sub.i−x.sub.i)+x.sub.i+b; and the expression (3) represents a third method for generating the code set P.sub.n,x.sub.i, indicating that P.sub.n,x.sub.i can be obtained by using a (n−1)th power of cyclic-right-shift operator (t.sub.rn).sup.n−1 or an equivalent (n−1)th power of cyclic-left-shift operator (t.sub.l1).sup.n−1 to act on the largest single fixed point subgroup L.sub.n,x.sub.i. The fixed point x.sub.i∈Z.sub.n indicates that all permutation vectors in the largest single fixed point subgroup L.sub.n,x.sub.i contain a fixed point x.sub.i and the other code elements are non-fixed points. When n is a non-prime number, all the above-mentioned sets formed by the curly braces {⋅} require an intersection operation with the symmetric group S.sub.n to guarantee that each element p.sub.n,x.sub.i is a permutation vector. This is because for any non-prime number n and all a∈Z.sub.n−1, when a does not satisfy GCD(a, n)=1, the scaling transformation f.sub.a,x.sub.i(l.sub.1,x.sub.i)=a(l.sub.1,x.sub.i−x.sub.i)+x.sub.i cannot guarantee that all vectors in the set L.sub.n,x.sub.i={a(l.sub.1,x.sub.i−x.sub.i)+x.sub.i|a∈Z.sub.n−1, x.sub.i, i∈Z.sub.n, l.sub.1,x.sub.i=[1 . . . n]} are permutation vectors, that is, |L.sub.n,x.sub.i|<n−1. If and only if n is a prime number, all the sets formed by the curly braces {⋅} can guarantee that P.sub.n,x.sub.i generated by three methods all contain n(n−1) permutation codes without the need of an intersection operation with the symmetric group S.sub.n, that is, L.sub.n,x.sub.i is a (n, n−1, n−1) permutation group or |L.sub.n,x.sub.i=n−1. GCD (a, n) represents a greatest common divisor between a∈Z.sub.n−1 and n, and GCD(a, n)=1 indicates that a∈Z.sub.n−1 and n are mutually exclusive.

(15) For any n>1, in the above three methods for generating the code set P.sub.n,x.sub.i of the (n, μ, d) permutation group code, the expression (3) P.sub.n,x.sub.i=S.sub.n∩{(t.sub.rn).sup.n−1L.sub.n,x.sub.i}=S.sub.n∩{(t.sub.l1).sup.n−1L.sub.n,x.sub.i} has the lowest computational complexity. For the convenience of description, the code set is hereinafter calculated by P.sub.n,x.sub.i=S.sub.n∩{(t.sub.l1).sup.n−1L.sub.n,x.sub.i}. If and only if n is a prime number, the code set P.sub.n,x.sub.i is a (n, n(n−1), n−1) permutation group code.

Example 1

(16) let n=7, which is a prime number, and let a fixed point x.sub.i=x.sub.7=7. The computation expression of L.sub.7,7 is L.sub.7,7={al.sub.1,x.sub.i|a∈Z.sub.6, l.sub.1,x.sub.i=[1234567]}, and thus a largest single fixed point subgroup in which the point x.sub.i=7 can be calculated as follow.

(17) $L_{7,7}=\left\{\begin{array}{c}1l_{1,7},\\ 2l_{1,7},\\ 3l_{1,7},\\ 4l_{1,7},\\ 5l_{1,7},\\ 6l_{1,7}\end{array}\right\}=\left\{\begin{array}{c}{l}_{1,7},\\ l_{2,7},\\ l_{3,7},\\ l_{4,7},\\ l_{5,7},\\ l_{6,7}\end{array}\right\}=\left\{\begin{array}{c}1\left[1234567\right],\\ 2\left[1234567\right],\\ 3\left[1234567\right],\\ 4\left[1234567\right],\\ 5\left[1234567\right],\\ 6\left[1234567\right]\end{array}\right\}=\left\{\begin{array}{c}1234567,\\ 2461357,\\ 3625147,\\ 4152637,\\ 5316427,\\ 6543217\end{array}\right\}$

(18) By using the (n−1=6)th powder of the cyclic-left-shift operator (t.sub.l1).sup.6 to act on the largest single fixed point subgroup L.sub.7,7, the following (7, 42, 6) permutation group code P.sub.7,7 can be obtained:

(19) $P_{7,7}={\left\{p_1,p_2,\mathrm{.Math.},p_{42}\right\}}_7=\left\{{\left(t_{l1}\right)}^6{L}_{7,7}\right\}=\left\{{\left(t_{l1}\right)}^6{l}_{1,7},{\left(t_{l1}\right)}^6{l}_{2,7},{\left(t_{l1}\right)}^6{l}_{3,7},{\left(t_{l1}\right)}^6{l}_{4,7},{\left(t_{l1}\right)}^6{l}_{5,7},{\left(t_{l1}\right)}^6{l}_{6,7}\right\}=\left\{\begin{array}{cccccc}1234567& 2461357& 3625147& 4152637& 5316427& 6543217\\ 2345671& 4613572& 6251473& 1526374& 3164275& 5432176\\ 3456712& 6135724& 2514736& 5263741& 1642753& 4321765\\ 4567123& 1357246& 5147362& 2637415& 6427531& 3217654\\ 5671234& 3572461& 1473625& 6374152& 4275316& 2176543\\ 6712345& 5724613& 4736251& 3741526& 2753164& 1765432\\ 7123456& 7246135& 7362514& 7415263& 7531642& 7654321\end{array}\right\}$

(20) Example 1 indicates that the code set P.sub.7,7 is a permutation group code with a code length of 7, a minimum distance of 6, a cardinality of 42 and an error-correcting capability of 5.

(21) Assuming that the transmitter transmits a signal it carrying information to a wired or wireless channel for transmission, this signal it is mapped to a signal point in a signal constellation diagram P.sub.n,x.sub.i formed by a (n, n(n−1), n−1) permutation group code, or equivalently, a signal π=[a.sub.1 a.sub.2 . . . a.sub.n] selected from the signal constellation diagram P.sub.n,x.sub.i is, as a binary information sequence of the transmitter, transmitted to a channel. Due to the interference in the channel, the receiver can only receive a vector [â.sub.1 â.sub.2 . . . â.sub.n] with a length of n defined in a real domain from the channel. If it is desired to use a decoding method with the optimal performance, a minimum distance decoding algorithm equivalent to maximum likelihood can be used. Since the received word is a vector defined in the real domain, the following minimum Euclidean distance decoding algorithm is employed.

(22) Minimum Euclidean distance decoding algorithm: let the transmitter transmit a codeword π=[a.sub.1 a.sub.2 . . . a.sub.n] selected from the code set P.sub.n,x.sub.i of the (n, n(n−1), n−1) permutation group code to a channel, a received word {circumflex over (π)}=[a.sub.1 a.sub.2 . . . a.sub.n] is input to a decoder for the (n, n(n−1), n−1) permutation group code, and then the decoder calculates the Euclidean distance between the received word {circumflex over (π)}=[a.sub.1 a.sub.2 . . . a.sub.n] and each codeword in the code set P.sub.n,x.sub.i, and selects a codeword {circumflex over (π)}=[a.sub.1 a.sub.2 . . . a.sub.n] with the smallest Euclidean distance from the received word {circumflex over (π)}=[a.sub.1 a.sub.2 . . . a.sub.n]:

(23) $\tilde{\pi }=\left[{\tilde{a}}_1{\tilde{a}}_2\mathrm{.Math.}{\tilde{a}}_n\right]=\arg \underset{\pi \in P_{n,x_i}}{\min }{d}_E\left(\hat{\pi },\pi \right)$
where d.sub.E({circumflex over (π)}, π) represents the Euclidean distance between the two vectors ft and it, i.e., d.sub.E({circumflex over (π)}, π)=√{square root over (Σ.sub.i=1.sup.n(â.sub.i−a.sub.i).sup.2)}. Then, {tilde over (π)}=[a.sub.1 a.sub.2 . . . a.sub.n] is output from the decoder as an accurate estimation of the transmitted codeword π=[a.sub.1 a.sub.2 . . . a.sub.n].

(24) The computation amount of the minimum Euclidean distance decoding algorithm for the (n, n(n−1), n−1) permutation group code is: (2n−1)n(n−1) additions, n.sup.2 (n−1) multiplications (exponentiation) and n(n−1) root square operations, and its computation complexity is at least O(n.sup.3). Due to the complexity of reaching the third power of the code length n, this decoding algorithm cannot meet the requirement of the practical communication system for the low complexity hardware implementation of the decoder. In order to find a simplified decoding algorithm with no performance loss compared to the minimum Euclidean distance decoding algorithm, it is necessary to use the characteristic of the (n, n(n−1), n−1) permutation group code that the error-correcting capability is d 1=n−2. The following example provides a valuable insight, which laid the foundation for the inventors to propose an efficient and low-complexity decoding method for a (n, n(n−1), n−1) permutation group code. In the following, with reference to the code set P.sub.7,7 in Example 1, it is analyzed why the error-correcting capability of the (7, 42, 6) permutation group code is d−1=n−2=5.

Example 2

(25) assuming that the transmitter transmits a signal carrying information to a channel, this signal is mapped to a signal point p=[5147362] in the signal constellation diagram P.sub.n,x.sub.i. This signal is actually a codeword in line 4 and column 3 of the code set P.sub.7,7 of the (7, 42, 6) permutation group code. Assuming that the receiver can correctly detect two code elements in the received vector with a length of n defined in the real domain (for example, an element in the 2nd position is 1, which is expressed as p(2)=1; an element in the 4-th position is 7, which is expressed as p(4)=7), the decoding algorithm in the receiver can correctly decode the transmitted codeword by the two known code elements. The reason is that the codeword in which the element in the 2nd position is 1 and the element in the 4-th position is 7 is unique in the code set P.sub.7,7, that is, a codeword in line 4 and column 3. This example also confirms that the (n, n(n−1), n−1) permutation group code has an error-correcting capability of d−1=n−2=5, namely, if two code elements are known, the codeword can be decoded correctly.

Technical Solution

(26) The technical solution is divided into two parts. The first part covers a decoding method for a (n, n(n−1), n−1) permutation group code based on coset partition, and the second part covers a decoder for the (n, n(n−1), n−1) permutation group code.

(27) Part 1: a complete algebraic decoding method for a (n, n(n−1), n−1) permutation group code based on coset partition

(28) The (n, n(n−1), n−1) permutation group code based on coset partition not only can be regarded as a constellation diagram with n(n−1) modulation signal points, but also can be regarded as a non-binary, non-linear and non-systematic error-correcting code with an error-correcting capability of d−1=n−2. According to the characteristic of the error-correcting capability of d−1=n−2, we propose the following complete algebraic decoding method for the (n, n(n−1), n−1) permutation group code based on coset partition.

(29) Complete algebraic decoding method: if and only if n is a prime number, let p(r.sub.1)=s.sub.1 and p(r.sub.2)=s.sub.2 be two code elements correctly detected from a received real vector, in which r.sub.1, r.sub.2∈Z.sub.n are their position indices, and s.sub.1, s.sub.2∈Z.sub.n are their element values, then all code elements in the codeword p∈P.sub.n can be calculated by the following steps:

(30) i) Let w∈Z.sub.n be an efficient solution of an expression (r.sub.1−r.sub.2)w=s.sub.1−s.sub.2(mod n).

(31) ii) Calculating each element in a permutation codeword p by using the w according to the following expression:
p(i)=(s.sub.1+(n−r.sub.1+i)w)(mod n), where i=1,2, . . . ,n.

(32) iii) Outputting a decoded codeword p=[p(1)p(2) . . . p(n−1)p(n)].

(33) The computation amount of this decoding method is: 2n+2 additions, n+1 multiplications and n+1 modulo operations.

Example 3

(34) a codeword p=[5147362] is selected from P.sub.7,7 in Example 1, and sent to a channel. Assuming that two elements p(2)=1 and p(4)=7 are correctly detected. Firstly, according to an expression (r.sub.1−r.sub.2)w≡s.sub.1−s.sub.2(mod n), (2−4)w=1−7(mod 7) and −2w=−6(mod 7) are obtained, thereby obtaining a solution of w=3. Then, each element in the codeword is calculated as follows:
p(1)=(s.sub.1+(n−r.sub.1+1)w)(mod n)=(1+(7−2+1)3)(mod 7)=5,
p(2)=(s.sub.1+(n−r.sub.1+2)w)(mod n)=(1+(7−2+2)3)(mod 7)=1,
p(3)=(s.sub.1+(n−r.sub.1+3)w)(mod n)=(1+(7−2+3)3)(mod 7)=4,
p(4)=(s.sub.1+(n−r.sub.1+4)w)(mod n)=(1+(7−2+4)3)(mod 7)=7,
P(5)=(s.sub.1+(n−r.sub.1+5)w)(mod n)=(1+(7−2+5)3)(mod 7)=3,
p(6)=(s.sub.1+(n−r.sub.1+6)w)(mod n)=(1+(7−2+6)3)(mod 7)=6,
P(7)=(s.sub.1+(n−r.sub.1+7)w)(mod n)=(1+(7−2+7)3)(mod 7)=2.

(35) The decoded codeword is p=[p(1)p(2)p(3)p(4)p(5)p(6)p(7)]=[5147362], which is identical to the transmitted codeword. Therefore, the complete algebraic decoding method can achieve error-free decoding.

(36) Part 2: a complete algebraic decoder for a (n, n(n−1), n−1) permutation group code based on coset partition

(37) The complete algebraic decoding method for a (n, n(n−1), n−1) permutation group code based on coset partition is implemented by the complete algebraic decoder.

(38) The principle structure of the complete algebraic decoder is mainly composed of four parts, including a number of independent n-dimensional registers, a basic principle circuit of an intermediate parameter w calculator, basic principle circuits of n single-code-element calculators operating in parallel, and a n-dimensional buffer for n code elements, as shown in FIG. 1.

(39) The independent n-dimensional registers are configured to respectively store parameters r.sub.1, r.sub.2, s.sub.1, s.sub.2, n and a code element position index i. The basic principle circuit of the intermediate parameter w calculator may be a calculator with a divider (FIG. 2) or a simplified calculator (FIG. 4). The basic principle circuit of the single-code-element calculator may be a basic principle circuit of a single-code-element calculator with a multiplier (FIG. 5) or a basic principle circuit of a simplified single-code-element calculator (FIG. 6). The n single-code-element calculators are configured to operate in parallel to simultaneously calculate n code elements. The n-dimensional buffer for n code elements are configured to store output results of the n single-code-element calculators operating in parallel to form a permutation codeword and output it as a decoded codeword.

(40) The basic principle circuit of the intermediate parameter w calculator with a divider is configured to calculate the intermediate parameter w=(s.sub.1−s.sub.2)/(r.sub.1−r.sub.2)(mod n), and is mainly composed of four parts: four independent n-dimensional registers, two two-input adders, a divider, and a modulo n operator mod n, as shown in FIG. 2.

(41) The position values r.sub.1, −r.sub.2 and the element values s.sub.1, −s.sub.2 of the two known code elements p(r.sub.1)=s.sub.1 and p(r.sub.2)=s.sub.2 are stored in the four independent n-dimensional registers, r.sub.1 and −r.sub.2 are input to one adder, s.sub.1 and −s.sub.2 are input to the other adder, outputs r.sub.1−r.sub.2 and s.sub.1−s.sub.2 of the two adders are simultaneously output to the divider, and the modulo n operator mod n performs a modulo operation of the outputs (s.sub.1−s.sub.2)/(r.sub.1−r.sub.2) of the divider and then outputs w. Another variation is as follow: two modulo n operators mod n are respectively disposed in front of the divider, so that (r.sub.1−r.sub.2)(mod n) and (s.sub.1−s.sub.2)(mod n) are input to the two input ends of the divider, and then the divider outputs w=(s.sub.1−s.sub.2)(mod n)/(r.sub.1−r.sub.2)(mod n).

(42) In order to eliminate the complicated divider and modulo n operator in the process of calculating the intermediate parameter w, a flowchart for calculating the intermediate parameter w is provided according to the working characteristics of the basic unit circuit.

(43) A flowchart for the simplified intermediate parameter w calculator: FIG. 3 shows a flowchart of the simplified calculator for solving the intermediate parameter w after removing the divider and the modulo n operator. After analyzing the calculation expression (r.sub.1−r.sub.2)w=(s.sub.1−s.sub.2)(mod n), the following features are found: firstly, (r.sub.1−r.sub.2) and (s.sub.1−s.sub.2) may be positive or negative numbers, and if negative, the negative number can be added with n to become a positive number, corresponding to performing a modulo n operation; secondly, when (r.sub.1−r.sub.2) and (s.sub.1−s.sub.2) are both positive numbers, w times of (r.sub.1−r.sub.2) is equal to (s.sub.1−s.sub.2); thirdly, w times of (r.sub.1−r.sub.2) corresponds to w times of accumulation of (r.sub.1−r.sub.2); and fourthly, when (r.sub.1−r.sub.2)=(s.sub.1−s.sub.2), w=1. Based on these four characteristics, a simplified flowchart for calculating w can be summarized.

(44) Position values r.sub.1, r.sub.2 and element values s.sub.1, s.sub.2 of the two known code elements p(r.sub.1)=s.sub.1 and p(r.sub.2)=s.sub.2 are input, and the intermediate parameter w is initialized to be w=1. u=r.sub.1 r.sub.2 and v=s.sub.1−s.sub.2 are respectively calculated. Values of u and v are respectively determined: if u>0, a value of u is directly output, and if u<0, then u=n+u, a value of u is output; similarly, if v>0, a value of v is directly output, and if v<0, then v=n+v, a value of v is output. The above process is used to replace the operation of the modulo n operator. The values of u and v are compared, if u=v, then w=1 is output; if u≠v, then w times of accumulation of u are performed so that uw=v (1<w≤n), and w is output.

(45) A circuit for calculating the intermediate parameter w, which is designed according to the idea of the flowchart provided in FIG. 3, falls within the protection scope of the disclosure. A basic principle circuit of a simplified intermediate parameter w calculator is provided below, but the intermediate parameter w calculator is not limited thereto.

(46) A basic principle circuit of a simplified intermediate parameter w calculator is mainly composed of five n-dimensional registers, two adders with carry bit C, two two-input adders, a n-dimensional NAND gate comparator, an enable control accumulator, and an enable control counter with feedback-plus-one operation, as shown FIG. 4. The basic principle circuit of the simplified intermediate parameter w calculator is provided to simply the intermediate parameter w calculator in FIG. 2 by removing the divider and the modulo n operator.

(47) Parameters r.sub.1, −r.sub.2, s.sub.1, −s.sub.2 and n are respectively stored in the five n-dimensional registers, and the counter has an initial value set to w=1. r.sub.1, −r.sub.2 and s.sub.1, −s.sub.2 output from the n-dimensional registers are respectively input to the two adders with carry bit C, and after the add operation, the respective double-throw switch is controlled by the value of the corresponding carry bit C.

(48) The two adders with carry bit C are configured to respectively calculate u=r.sub.1−r.sub.2 and v=s.sub.1−s.sub.2. When u<0, the carry bit C.sub.1=1, the corresponding double-throw switch is thrown to the right, u enters the two-input adder 1 to achieve an add operation of n+u, and u is output and enters the comparator through the accumulator; when u>0, the carry bit C.sub.1=0, the corresponding double-throw switch is thrown to the left, u enters the comparator through the accumulator. When v<0, the carry bit C.sub.2=1, the corresponding double-throw switch is thrown to the left, v enters the two-input adder 2 to achieve an add operation of n+v, and v is output and directly enters the comparator; when v>0, the carry bit C.sub.2=0, the corresponding double-throw switch is thrown to the right, and v directly enters the comparator.

(49) When the enable signal E.sub.1=1, the accumulator performs an add operation of u+u; when the enable signal E.sub.1=0, the accumulator directly output u to the comparator without performing the add operation.

(50) The comparator compares u and v. If u=v, a low level enable signal E.sub.2=1 is output, so that the counter directly outputs w=1 without performing the feedback-plus-one operation.

(51) If u≠v, the accumulator has an enable signal E.sub.1=1, and returns the current output u to its input end for accumulating u once; meanwhile, the counter has an enable signal Ē.sub.2=1, so that the feedback-plus-one operation is performed on the current output w; as long as u≠v, the comparator, the accumulator and the counter repeat the above operations until u=v, resulting in that Ē.sub.2=1, and the accumulator stops performing the feedback-plus-one operation, and outputs a value of w.

(52) When n is not too large, the time taken to perform w times of accumulation of u does not exceed the time taken by the divider to perform an operation once, and then the simplification from FIG. 2 to FIG. 4 is practical.

(53) The basic principle circuit of the single-code-element calculator with the multiplier is mainly composed of five independent n-dimensional registers, a three-input adder, a two-input multiplier, a two-input adder and a modulo n operator, as shown FIG. 5. In a case of two known code elements, the decoder in FIG. 5 is configured to calculate each code element in the permutation code, i.e., p(i)=(s.sub.1+(n−r.sub.1+i)w)(mod n), i=1, 2, . . . , n−1. When i=n, p(n)=(s.sub.1+(n−r.sub.1)w)(mod n).

(54) The five independent n-dimensional registers are configured to respectively store a code element position index i, a code length n, −r.sub.1, an intermediate parameter w, and s.sub.1. Firstly, i, n and −r.sub.1 are input to the three-input adder to achieve an add operation of (n−r.sub.1+i). Secondly, the operation result of the adder and w output from the n-dimensional register are input to the multiplier to achieve a multiply operation of (n−r.sub.1+i)w. Then, the operation result of the multiplier and s.sub.1 output from the n-dimensional register are input to the two-input adder to achieve an add operation of (s.sub.1+(n−r.sub.1+i)w). Finally, a modulo n operation is performed on the operation result of the adder to output an i-th code element p(i) in the decode codeword.

(55) In order to eliminate the complicated operation circuit of the multiplier in the process of calculating a single code element, the multiply operation of (n−r.sub.1+i) and w may be regarded as w times of accumulation of (n−r.sub.1+i), that is, the multiplier may be converted to an accumulator controlled by a counter with a cycle-minus-one operation of an intermediate parameter w.

(56) The basic principle circuit of the simplified single-code-element calculator is mainly composed of four n-dimensional registers, a three-input adder, an enable control accumulator, a counter with a cycle-minus-one operation of an intermediate parameter w, a two-input adder and a modulo n operator, as shown in FIG. 6. In a case of two known code elements, the adder and the counter with the cycle-minus-one operation of the intermediate parameter w in FIG. 6 are used instead of the multiplier in FIG. 5 to simplify the principle circuit of the single-code-element calculator.

(57) The four n-dimensional registers are configured to respectively store a code element position index i, a code length n, −r.sub.1 and s.sub.1. Firstly, i, n and −r.sub.1 are input to the three-input adder to achieve an add operation of (n−r.sub.1+i). Secondly, the operation result of the adder is input to the enable control accumulator to achieve w times of accumulation of (n−r.sub.1+i), in which an operation of w−1 is performed for each accumulation; when w≠0, the accumulator has an enable signal E=1, so that the accumulator continues to perform the accumulation operation on (n−r.sub.1+i), until w is reduced to 0, and then the accumulator has an enable signal E=0, so that the accumulator stops the accumulation and outputs a result to one input end of the two-input adder. This process is equivalent to the multiply operation of (n−r.sub.1+i)w. Then, the operation result of the multiplier and s.sub.1 output from the n-dimensional register are input to the two-input adder to achieve an add operation of (s.sub.1+(n−r.sub.1+i)w). Finally, a modulo n operation is performed on the operation result of the adder to output the i-th code element p(i) in the decode codeword.

(58) When n is not too large, the time taken to perform w times of accumulation of a number does not exceed the time taken by the divider to perform an operation once, and then the simplification from FIG. 5 to FIG. 6 is practical.

(59) The architecture of the complete algebraic decoder is mainly composed of an intermediate parameter w calculator, n single-code-element calculators and a n-input and single-output buffer. The intermediate parameter calculator may be implemented by the intermediate parameter w calculator with the divider in FIG. 2, the simplified intermediate parameter w calculator in FIG. 4, or any intermediate parameter w calculator designed according to the flowchart of the simplified intermediate parameter w calculator. The single-code-element calculator may be implemented by the single-code-element calculator with the multiplier in FIG. 5, the simplified single-code-element calculator in FIG. 6, or any calculating circuit designed to achieve p(i)=(s.sub.1+(n−r.sub.1+i)w)(mod n) (i=1, 2, . . . , n−1).

(60) An optional architecture of the complete algebraic decoder is mainly composed of a simplified w calculator, n simplified single-code-element calculators operating in parallel and a n-input and single-output buffer, shown in FIG. 7.

(61) The signal flow of the architecture of the complete algebraic decoder is described as follows: the w value of the simplified intermediate parameter w calculator enters the n counters with the w cycle-minus-one operation operating in parallel, respectively; when the accumulators in the n simplified single-code-element calculators operating in parallel acquire the output results (n−r.sub.1+i) of the three-input adder, where i−1, 2, . . . , n, the respective counter with the w cycle-minus-one operation provides an enable signal E=1 for each cycle-minus-one operation, so that the accumulator performs the accumulation operation on (n−r.sub.1+i) once, until w in the counter with the cycle-minus-one operation of w is reduced to 0, and then the accumulator stops the accumulation operation and outputs a calculation result (n−r.sub.1+i)w; the calculation result (n−r.sub.1+i)w and s.sub.1 are input together to the two-input adder to achieve an operation of s.sub.1+(n−r.sub.1+i)w; a modulo n operation is performed on the operation result of the two-input adder; finally, the output results of the n simplified single-code-element calculators operating in parallel are input to a n-dimensional buffer to form a decode codeword p=[p(1)p(2) . . . p(n)].

(62) It should be readily understood to those skilled in the art that the above description is only preferred embodiments of the present disclosure, and does not limit the scope of the present disclosure. Any change, equivalent substitution and modification made without departing from the spirit and scope of the present disclosure should be included within the scope of the protection of the present disclosure.