Methods for encoding and decoding sparse code and orthogonal sparse superposition code

Abstract

The inventive concept relates to method for encoding and decoding sparse codes and orthogonal sparse superposition codes. A sparse code encoding method which is to be performed by an encoding apparatus, according to an embodiment of the inventive concept may include selecting an index set that is a part of a code block by using an information bit, and mapping a codeword less than a preset size to the selected index set.

Claims

1. A sparse code encoding method which is to be performed by an encoding apparatus, comprising: dividing, by a bit splitter, a plurality of information bits into multiple information bits, including a first information bit having a first length and a second information bit having a second length; selecting an index set that is a part of a code block by using the first information bit; generating a sparse code, wherein the generating comprises mapping a codeword less than a preset size to the selected index set; generating, by an encoder, a codeword using the second information bit; and generating a modulated codeword by performing modulation, wherein performing the modulation comprises allocating a modulation symbol to the generated codeword, wherein: the dividing, the selecting, and the generating are part of the sparse code encoding method performed at the encoding apparatus; the code block comprises elements associated with code positions; each of the elements is represented consecutively at a corresponding code position of the code positions; the selecting of the index set includes selecting one or more elements at corresponding one or more code positions in the code block using the first information bit; the index set represents the one or more code positions in the code block; the one or more code positions are one or more non-zero positions in the code block; the elements comprise the one or more elements, and the code positions comprise the one or more code positions; the codeword less than the preset size represents a subcodeword; and mapping the codeword less than the preset size to the selected index set comprises mapping the modulated codeword to the selected index set.

2. An orthogonal sparse superposition code encoding method which is to be performed by an encoding apparatus, comprising: encoding a plurality of information bits into encoded information bits; dividing the encoded information bits into multiple information bits, including a first encoded information bit; selecting a first index set from a first code block in a first layer using the first encoded information bit, and sequentially selecting a next index set from a next code block in a next layer of one or more remaining code blocks using a next encoded information bit, wherein each of the first index set and the next index set is mutually exclusive so that the first index set and the next index set are different from one another, wherein layers comprise the first layer, the next layer, and one or more remaining layers; sequentially generating a plurality of subcodewords by allocating modulation symbols to index sets selected in the layers respectively; generating a sparse superposition code by combining the generated plurality of subcodewords; and performing power spreading of the generated sparse superposition code using unitary transform to spread transmit power over channel use, wherein: the encoding, the dividing, the selecting, the sequentially generating, and the generating are part of the orthogonal sparse superposition code encoding method performed at the encoding apparatus; each of the first code block and the next code block comprises elements associated with code positions; each of the elements is represented consecutively at a corresponding code position of the code positions; the selecting of the first index set includes selecting one or more elements at corresponding one or more code positions in the first code block using the first encoded information bit; the first index set represents the one or more code positions in the first code block; the one or more code positions in the first code block are one or more non-zero positions in the first code block; and the elements of the first code block comprise the one or more elements of the first code block, and the code positions of the first code block comprise the one or more code positions in the first code block.

3. The orthogonal sparse superposition code encoding method of claim 2, wherein a next subcodeword maintains orthogonality with a first subcodeword when the plurality of subcodewords are sequentially generated.

4. The orthogonal sparse superposition code encoding method of claim 2, wherein a next subcodeword maintains near-orthogonality with a first subcodeword when the plurality of subcodewords are sequentially generated.

5. The orthogonal sparse superposition code encoding method of claim 4, wherein the sequentially selecting of the next index set includes generating a projection matrix corresponding to the first index set used in the first layer, and when energy is less than a preset delta in a case where the generated projection matrix is projected, using a corresponding index as the next index set.

6. The orthogonal sparse superposition code encoding method of claim 5, wherein the sequentially selecting of the next index set includes controlling a degree of superposition interference by adjusting the delta.

7. The orthogonal sparse superposition code encoding method of claim 2, wherein the sequentially selecting of the next index set includes sequentially selecting an index set for each section in a code block which has been divided into a plurality of sections.

8. A sparse code decoding method which is to be performed by a decoding apparatus, comprising: sorting reception signals in an order of size; detecting a preset number of uppermost or lowermost index set from the reception signals sorted in the order of size; and performing decoding on a sparse code by using a reception signal carried on the detected index set, wherein: the reception signals comprise positions that are consecutive; each of the reception signals is associated with a corresponding position of the positions; sorting the reception signals comprises re-ordering the positions of the reception signals in an order of a size of each of the reception signals at the corresponding position; the uppermost index set represents uppermost one or more positions in the reception signals after the re-ordering; the lowermost index setrepresent lowermost one or more positions in the reception signals after the re-ordering; the size of the reception signal carried on the uppermost index set is larger than the size of the reception signal carried on the lowermost index set; the detected index set is the uppermost index set or the lowermost index set; the performing of the decoding includes detecting a subcodeword by allocating a corresponding modulation symbol to an element of the detected index set; and the element of the detected index set corresponds to the reception signal carried on the detected index set.

9. The sparse code decoding method of claim 8, wherein the performing of the decoding includes determining the modulation symbol corresponding to the element of the detected index set.

10. An orthogonal sparse superposition code decoding method which is to be performed by a decoding apparatus, comprising: detecting a support set that is a non-zero position from a reception signal; identifying a set of subcodewords from the detected support set; and performing decoding on the identified set of subcodewords, wherein: the reception signal comprises elements associated with positions that are consecutive; each of the elements is associated with a corresponding position of the positions; the identifying of the set of subcodewords includes identifying the set of subcodewords through comparison of a size of probabilities belonging to each support set; each support set represents a position in the reception signal that is a non-zero position in the reception signal; and the performing of the decoding includes determining a modulation symbol corresponding to an element of the identified set of subcodewords and detecting a subcodeword by allocating the determined modulation symbol to the element.

11. The orthogonal sparse superposition code decoding method of claim 10, wherein the detecting of the support set includes sequentially detecting a support set that is a non-zero position for each section from a reception signal which has been divided into a plurality of sections.

12. The orthogonal sparse superposition code decoding method of claim 10, wherein the detecting of the support set includes sequentially detecting a next support set that is a non-zero position from remaining reception signals except a previous support set used in a previous section.

Description

BRIEF DESCRIPTION OF THE FIGURES

(1) The above and other objects and features will become apparent from the following description with reference to the following figures, wherein like reference numerals refer to like parts throughout the various figures unless otherwise specified, and wherein:

(2) FIG. 1 is a diagram illustrating an operation of an encoding apparatus for sparse codes according to an embodiment of the inventive concept;

(3) FIGS. 2 and 3 are diagrams for describing an operation of an encoding apparatus for sparse codes according to another embodiment of the inventive concept;

(4) FIG. 4 is a diagram for describing an orthogonal sparse superposition code according to another embodiment of the inventive concept;

(5) FIG. 5 is a diagram illustrating an operation of an encoding apparatus for orthogonal sparse superposition codes according to another embodiment of the inventive concept;

(6) FIG. 6 is a flowchart for describing an encoding method for orthogonal sparse superposition codes according to another embodiment of the inventive concept;

(7) FIG. 7 is a diagram illustrating an operation of an encoding apparatus for orthogonal sparse superposition codes according to another embodiment of the inventive concept;

(8) FIG. 8 is a diagram illustrating a successive encoding operation using precoding according to another embodiment of the inventive concept;

(9) FIG. 9 is a diagram illustrating an operation of a decoding apparatus for sparse codes according to another embodiment of the inventive concept;

(10) FIGS. 10 and 11 are diagrams illustrating an operation example of a decoding method for sparse codes according to another embodiment of the inventive concept;

(11) FIGS. 12 and 13 are diagrams illustrating an operation of a decoding apparatus for orthogonal sparse superposition code according to another embodiment of the inventive concept;

(12) FIG. 14 is a diagram illustrating an operation of a decoding apparatus for an orthogonal sparse superposition code according to another embodiment of the inventive concept using a probability equation.

(13) FIG. 15 is a diagram illustrating an operation of a decoding apparatus for an orthogonal sparse superposition code according to still another embodiment of the inventive concept using a probability equation.

(14) FIG. 16 is a diagram showing a parallel decoding structure using precoding according to another embodiment of the inventive concept;

(15) FIG. 17 is a block diagram for describing configurations of an encoding apparatus and a decoding apparatus according to an embodiment of the inventive concept;

(16) FIG. 18 is a diagram showing results of comparison between an embodiment of the inventive concept and a conventional code when a code length is 32;

(17) FIGS. 19 to 21 are diagrams showing results of comparison between an embodiment of the inventive concept and conventional codes when code lengths are 64, 128 and 256, respectively;

(18) FIG. 22 is a diagram showing a result of comparison between an embodiment of the inventive concept and a conventional code when a block length increases while lowering a code rate;

(19) FIG. 23 is a diagram showing analysis of BLER for a single layered orthogonal sparse superposition code;

(20) FIG. 24 is a diagram showing analysis of BLER for a two-layered orthogonal sparse superposition code; and

(21) FIG. 25 is a diagram showing a result of comparison between an embodiment of the inventive concept and a conventional code when a code length is 256.

DETAILED DESCRIPTION

(22) The inventive concept may apply various transformations and have various embodiments, and specific embodiments will be illustrated in the drawings and described in detail in the detailed description. However, this is not intended to limit the inventive concept to a specific embodiment, and it may be understood to include all conversions, equivalents, or substitutes included in the technical spirit and scope of the inventive concept. In the following description of the inventive concept, detailed description of known related arts will be omitted when it is determined that the gist of the inventive concept may be unnecessarily obscured.

(23) The terms such as ‘first’, ‘second’, or the like may be used to denote various components, but the components are not limited by the terms. The terms are used merely for the purpose to distinguish a component from the other component.

(24) Terms used in the disclosure are used to describe specified embodiments and are not intended to limit the scope of the inventive concept. The terms used in the inventive concept have been selected from among general terms that are currently widely used as possible while taking functions of the inventive concept into consideration, but this may vary according to the intention, precedent, or the emergence of new technologies of the skilled person in the field. In addition, in certain cases, there are terms arbitrarily selected by the applicant, and in this case, the meaning of the terms will be described in detail in the description of the corresponding invention. Therefore, the terms used in the inventive concept should be defined based on the meaning of the term and the overall contents of the inventive concept, not a simple name of the term.

(25) As used herein, singular forms may include plural forms as well unless the context clearly indicates otherwise. It will be further understood that the terms “comprise,” “comprising,” “having,” “include,” “including” and/or variations thereof, when used in this specification, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof.

(26) Hereinafter, embodiments of the inventive concept will be described in detail with reference to the accompanying drawings, and in the description with reference to the accompanying drawings, the same or corresponding components are allocated with the same reference numbers, and redundant descriptions thereof will be omitted.

(27) Before describing embodiments of the inventive concept, relevant terms and the like will be described.

(28) N∈.sup.+ means the block length of a code. x.sub.l=[.sub.1, .sub.2, . . . , .sub.N].sup.T is a sparse message vector.

(29) Furthermore, a set of signal levels for the element of is defined. is the number of non-zero signal levels that may be allocated to for ∈[L]. In addition, the signal level set for a non-zero value of the ∈[L]-th codeword vector is as shown in [Equation 1].
={.sub.,1,.sub.,2, . . . ,,}  [Equation 1]

(30) where, .sub.,i≠0 and ||= for i∈[].

(31) is defined as a union of L signal level sets, that is, = is generally selected from an arbitrary pulse amplitude modulation (PAM) signal set. A multi-level modulation set is defined as in [Equation 2] by the union of L signal level sets.
=  [Equation 2]

(32) For example, in the case of L=2, .sub.1={1, −1} and .sub.2={2, −2}, the multi-level signal set becomes ={−2, −1, 1, 2}.

(33) Next, an index subset and a support set will be described.

(34) A subset is defined as in [Equation 3] for ∈[L].
.Math.{1,2, . . . ,N}  [Equation 3]

(35) Here, ||≤N for l∈[L]. In addition, for l∈[L], the support set of is defined by [Equation 4].
={n|.sub.,n∈}  [Equation 4]

(36) The cardinality of is set to , that is, ||= for l∈[L].

(37) Thus, the l∈[L]th subcodeword vector x.sub.l is a sparse vector, that is, ∥x∥.sub.0= for l∈[L].

(38) An arbitrary set of supports for satisfies two characteristics.

(39) As a first characteristic, is a subset of , that is, ⊂.

(40) As a second feature, all support sets are mutually exclusive. That's ∩=∅ for all i, j∈[L].

(41) The second characteristic denotes ∩{}=∅ for ∈[L]. The second characteristic is referred to as an orthogonal characteristic.

(42) Information bit mapping and de-mapping will be described.

(43) A function is considered, which maps an information bit vector with a length of

(44) $=.Math.{\log }_2\left(\left(\begin{array}{c}.Math.\\ K_{\ell }\end{array}\right)\right).Math.+{\log }_2\left(.Math..Math.\right)$
to by uniformly selecting the index in and allocating signal levels .sub.,i to non-zero supports uniformly. This mapping function is defined by [Equation 5].
:.fwdarw.{0,}||  [Equation 5]

(45) Thus, each subcodeword is generated by =(). Similarly, there is a Bijection inverse mapping from to , that is, =() for ∈[L].

(46) FIG. 1 is a diagram illustrating an operation of an encoding apparatus for sparse codes according to an embodiment of the inventive concept.

(47) An encoding apparatus 100 for sparse codes according to an embodiment of the inventive concept may map information bits to an index of a vector. In this case, the encoding apparatus 100 may map a codeword having another size less than a preset size to an index set to generate a sparse code. To this end, the encoding apparatus 100 may map a codeword having a specific very small length to the selected index set while using the information bits to select a part of a code block.

(48) As shown in FIG. 1, the encoding apparatus 100 may divide an information bit u into an information bit u.sub.1 having a length of B.sub.1 and an information bit u.sub.2 having a length of B.sub.2. u, u.sub.1 and u.sub.2 may satisfy, u∈.sub.2.sup.B, u.sub.1 ∈.sub.2.sup.B.sup.1 and u.sub.2 ∈.sub.2.sup.B.sup.2, respectively.

(49) In addition, the encoding apparatus 100 may select K index sets from among N elements having a code block length using the information bits u.sub.1. The selected index sets may represent a .sub.1 support set that is a non-zero position.

(50) In addition, the encoding apparatus 100 may generate a codeword c∈.sub.2.sup.K using the information bit u.sub.2 through an encoder. The encoding apparatus 100 may perform modulation by allocating a modulation symbol to the generated codeword c to generate v∈.sup.K.

(51) Further, the encoding apparatus 100 may generate a sparse code x by mapping the codeword v to the selected support set .sub.1. v and x may satisfy

(52) $v\in K^{},=v,\mathrm{and}x\in {\left\{\left\{0\right\}.Math.\right\}}^N\mathrm{satisfy}R=\frac{B_1+B_2}{N}=\frac{.Math.{\log }_2\left(\left(\begin{array}{c}N\\ K\end{array}\right)\right).Math.+{\mathrm{KR}}_2}{N}.$
A code rate may

(53) FIGS. 2 and 3 are diagrams for describing an operation of an encoding apparatus for sparse codes according to another embodiment of the inventive concept.

(54) Compared with FIG. 1, the encoding apparatus 100 for sparse codes according to another embodiment of the inventive shown in FIG. 2 may perform sparse coded modulation. The encoding apparatus 100 may further includes a first encoder (Encoder 1). The first encoder may encode information bits u.sub.1. The encoding apparatus 100 may select K index sets from among N elements having a code block length by using the encoded information bits u.sub.1. A second encoder (Encoder 2) may generate a codeword c from the information bits u.sub.2 through an encoder as in FIG. 1.

(55) Compared with FIG. 1, the encoding apparatus 100 for sparse codes according to another embodiment of the inventive shown in FIG. 3 may perform sparse coded modulation. The encoding apparatus 100 may perform encoding through an encoder in advance before dividing the information bits. Then, the encoded information bits u are divided into encoded information bits u.sub.1 and encoded information bits u.sub.2. Further, the encoding apparatus 100 may select K index sets from among N elements having a code block length by using the encoded information bits u.sub.1. In addition, the encoding apparatus 100 may perform modulation using the encoded information bits u.sub.2.

(56) FIG. 4 is a diagram for describing an orthogonal sparse superposition code according to another embodiment of the inventive concept.

(57) Orthogonal sparse superposition coding according to another embodiment of the inventive concept is to a method of mapping information by superposition several sparse codes in several layers so as not to interfere with each other. Orthogonal sparse superposition coding according to another embodiment of the inventive concept is to combine L different sparse codes of a number of layers so as not to superpose each other. To this end, successive support elimination encoding is performed.

(58) Referring to FIG. 4, an example of a method of superposing two codewords each having a codeword length of 8 will be described. A total of 10 bits may be generated as a codeword having a length of 8.

(59) The first subcodeword is generated. One of eight indices is selected as a fourth element. Here, the amount of information is 3 bits. The selected fourth element is mapped to a black symbol set 401. In the case of Binary Phase Shift Keying (BPSK), the amount of information is 1 bit.

(60) A second subcodeword is generated. Information is mapped in a method for selecting two of the remaining seven elements except the fourth element used in the first subcodeword. Two of the seven indices are selected as first and seventh elements. Here, the amount of information is 4 bits. The selected first and seventh elements are mapped to a red symbol set 402. In the case of BPSK, the amount of information is a total of 2 bits.

(61) FIG. 5 is a diagram illustrating an operation of an encoding apparatus for orthogonal sparse superposition codes according to another embodiment of the inventive concept.

(62) The encoding apparatus 100 for orthogonal sparse superposition codes according to another embodiment of the inventive concept may continuously perform a modulation operation of superposing information on L layers without interference with each other.

(63) As shown in FIG. 5, the encoding apparatus 100 may continuously map codewords to L different subcodewords. Index sets respectively selected in layers are mutually exclusive. The encoding operation may consist of L phases (L phases).

(64) Specifically, the encoding apparatus 100 may divide a codeword U into a codeword u.sub.1, a codeword u.sub.2, . . . and a codeword u.sub.L. u, u.sub.1, u.sub.2, and u.sub.L may satisfy u∈.sub.2.sup.B, u.sub.1∈.sub.2.sup.B.sup.1, u.sub.2∈.sub.2.sup.B.sup.2, . . . , u.sub.L∈.sub.2.sup.B.sup.L, respectively.

(65) In the first phase, the encoding apparatus 100 may select K.sub.1 index sets from among || elements to encode the codeword u.sub.1 into a sparse vector x.sub.1. The selected index sets may represent a support set that is a non-zero position. In addition, the encoding apparatus 100 may uniformly allocate the modulation symbols .sub.1 to K.sub.1 index sets that are non-zero of the subcodeword x.sub.1 to finally generate the subcodeword x.sub.1.

(66) In the second phase, the encoding apparatus 100 may select K.sub.2 index sets from among || elements that is a code block length using the codeword u.sub.2. The selected index set represents a support set .sub.2 that is a non-zero position. Herein, includes unselected remaining indices other than the support set .sub.1 selected when generating a subcodeword x.sub.1. may satisfy =[N]\. In addition, the encoding apparatus 100 may generate a subcodeword x.sub.2 by uniformly allocating the modulation symbols .sub.2 to K.sub.2 index sets that are non-zero of the subcodeword x.sub.2.

(67) Thereafter, the encoding apparatus 100 may successfully apply the same principle up to the Lth phase.

(68) In the last phase, the encoding apparatus 100 may select K.sub.L index sets from among |.sub.L| elements that is a code block length by using a codeword u.sub.L. The selected index sets may represent a support set .sub.L that is a non-zero position. Herein .sub.L may include unselected remaining indices other than the support sets .sub.1, .sub.2, . . . , .sub.L-1 selected when generating subcodewords x.sub.1, x.sub.2, . . . , x.sub.L-1. .sub.L may satisfy

(69) ${𝒩}_{\ell }.Math.\left\{\stackrel{\ell -1}{\underset{j=1}{.Math.}}{j}_{}\right\}=\varnothing .$
In addition, the encoding apparatus 100 may generates a subcodeword x.sub.L by uniformly allocating the modulation symbols .sub.L to K.sub.L index sets that are non-zero of the subcodeword x.sub.L. With this configuration, the support sets of subcodewords are mutually exclusive (.sub.i∩.sub.j=∅).

(70) When the encoding apparatus 100 generates L subcodewords, the codewords are configured by superposition of the L subcodewords. P.sub.1 may be defined as power allocated to the 1-th subcodeword. The orthogonal index superposition code is as shown in [Equation 6] below.

(71) $\begin{array}{cc}x=\underset{\ell =1}{\overset{L}{.Math.}}\sqrt{P_{\ell }}{x}_{\ell }& \left[\mathrm{Equation}6\right]\end{array}$

(72) In Equation 6, =P. Further, the support set that is non-zero of x is an union. That is, may be equal to [Equation 7] below.
=  [Equation 7]

(73) In Equation 7,

(74) ${.Math.x.Math.}_0=\underset{\ell =1}{\overset{L}{.Math.}}{K}_{\ell }\le N.$

(75) The encoding apparatus 100 may use a unitary transform U∈.sup.N×N to obtain a pre-coded codeword vector (c=Ux) in order to spread transmit power over use of N channels. The unitary matrix may be advantageous in reducing the Peak-to-Average-Power-Ratio (PAPR) in hardware implementations.

(76) Meanwhile, the decoding possibility will be described.

(77) The orthogonal index superposition code may be decoded, when all power-weighted non-zero signal levels are different, that is, when non-zero signals level of and are uniquely present, a.sub.l,i.Math.∪.sub.j≠i.sub.j. In the case of noise-free, when a decoding apparatus 200 observes

(78) $x=\underset{\ell =1}{\overset{L}{.Math.}}{x}_{\ell },$
the decoding apparatus 200 may identify L different subcodewords using a set of modulated signal levels that are distinct for uniquely determined . After that, the decoding apparatus 200 may perrform inverse mapping from to to obtain information bits , that is, =() for .

(79) The code rate will be described. The th subcodeword may carry information bits using N channels. The code rate of the th codeword may be expressed as in [Equation 8].

(80) $\begin{array}{cc}{R}_{\ell }=\frac{B_{\ell }}{N}& \left[\mathrm{Equation}8\right]\end{array}$

(81) As a result, the rate of the orthogonal index superposition code may be expressed as in [Equation 9].

(82) $\begin{array}{cc}R=\frac{\underset{\ell =1}{\overset{L}{.Math.}}{B}_{\ell }}{N}& \left[\mathrm{Equation}9\right]\end{array}$

(83) The encoding method according to the embodiments of the inventive concept may generate a code having a very flexible rate by appropriately selecting code parameters including N, L, , , and for . For a given code rate

(84) $R=\frac{\underset{\ell =1}{\overset{L}{.Math.}}{B}_{\ell }}{N}$
and the block length N, the code parameters may be optimized to minimize decoding errors.

(85) The average transmit power will be described. The average transmit power for orthogonal index superposition codes may be calculated. It should be noted that the number of codewords for is , and the codewords are evenly distributed for . Therefore, the average power of may be expressed as in [Equation 10].

(86) 0$\begin{array}{cc}𝔼\left[{.Math.x_{\ell }.Math.}_2^2\right]=\frac{K_{\ell }\underset{i=1}{\overset{.Math.{𝒜}_{\ell }.Math.}{.Math.}}{a}_{\ell ,i}^2}{N}& \left[\mathrm{Equation}10\right]\end{array}$

(87) Since each subcodeword vector is independently generated, the average power of x may be expressed as in [Equation 11].

(88) $\begin{array}{cc}{E}_s=\left[{.Math.x.Math.}_2^2\right]=\frac{\underset{\ell =1}{\overset{L}{.Math.}}{K}_{\ell }\underset{i=1}{\overset{.Math.{𝒜}_{\ell }.Math.}{.Math.}}{a}_{\ell ,i}^2}{.Math.{\ell }_{}.Math.N}& \left[\mathrm{Equation}11\right]\end{array}$

(89) In order to minimize the average transmit power, the encoding parameters .sub.,i, and should be carefully selected.

(90) The minimum distance of the code will be described. P.sub.1= . . . =P.sub.L is assumed. A codebook with a size of 2.sup.NR may be represented by

(91) $𝒞=\left\{c^1,c^2,\mathrm{.Math.},c^{2^{\mathrm{NR}}}\right\}.$
c.sup.j is the jth codeword of the orthogonal index superposition code. The minimum distance of the codebook may be defined by [Equation 12].

(92) $\begin{array}{cc}{d}_{\min }\left(𝒞\right)=\underset{i,j\in \left[2^{\mathrm{NR}}\right]}{\min }{.Math.c^i-c^j.Math.}_2& \left[\mathrm{Equation}12\right]\end{array}$

(93) Here, a coding gain of

(94) $\gamma 𝒸\left(𝒞\right)=\frac{d_{\min }^2\left(𝒞\right)}{E_b}=\frac{d_{\min }^2\left(𝒞\right)}{E_s/\left(2R\right)}$
is obtained.

(95) Some examples of coding schemes according to embodiments of the inventive concept will be described.

(96) Example 1: For ease of description, attention is paid to the symmetric case of [N, L]=[48, 2] and K.sub.1=K.sub.2=2. Further, two PAM sets .sub.1={−1, 1} and .sub.2={−2, 2} having the same power allocation P.sub.1=P.sub.2=1 are considered. In this example, an orthogonal index superposition code having a rate of R=1/2 and a block length of 48, that is, [N, K]=[48, 24] is constructed. The encoding apparatus 100 may generate four subcodeword vectors using a successive non-superposition index superposition method. The encoding apparatus 100 may map

(97) $B_1=.Math.{\log }_2\left(\left(\begin{array}{c}48\\ 2\end{array}\right)2^2\right).Math.=12$
information bits to x.sub.1 by selecting two non-zero positions and allocating them to 1 or −1 uniformly. In the second stage, the encoding apparatus 100 may map

(98) $B_2=.Math.{\log }_2\left(\left(\begin{array}{c}46\\ 2\end{array}\right)2^2\right).Math.=12$
information bits to x.sub.2 by selecting two non-zero positions in the index set that do not overlap the index set .sub.1, that is, the index set =[N]\.sub.1. The encoding apparatus 100 may uniformly allocate 2 or −2 to non-zero elements in x.sub.2. Since each subcodeword has a ternary alphabet, the superposition code may become [Equation 13].
c=x.sub.1+x.sub.1∈{−2,−1,0,1,2}.sup.48

(99) This code has an alphabetical size of 5 and the codeword is sparse (i.e. ∥c∥.sub.0=4). The normalized average transmit power per channel use becomes [Equation 14].

(100) $\begin{array}{cc}{E}_s=\frac{𝔼\left[{.Math.x.Math.}_2^2\right]}{N}=\frac{4}{48}=\frac{2}{48}=\frac{1}{8}& \left[\mathrm{Equation}14\right]\end{array}$

(101) Since the minimum distance of this code is 2, the normalized minimum distance may be given by [Equation 15].

(102) $\begin{array}{cc}\frac{d_{\min }^2}{E_s/\left(2R\right)}=\frac{2}{1/8}=16& \left[\mathrm{Equation}15\right]\end{array}$

(103) This example may demonstrate that an average transmit power per channel of an orthogonal index superposed code may be very small compared to a conventional coding scheme with binary phase shift keying modulation. For example, in the case of a convolutional code with [N, K]=[48, 24], the normalized average transmit power is 1.

(104) On the other hand, to further emphasize the importance of the code construction method, several will be described.

(105) Referring to the orthogonal characteristic, the most prominent characteristic of the orthogonal index superposition code guarantees the orthogonal characteristic, indicating that all support sets are mutually exclusive, that is, .sub.i∩.sub.j=∅ for all i, j∈[L]. This characteristic makes it easy to perform decoding in a computationally efficient manner. In addition, the characteristic may not be obtained from other conventional sparse superposition codes or conventional superposition codes. This orthogonality in the selection of the support set is achieved by a continuous multi-phase encoding scheme according to embodiments of the inventive concept.

(106) Referring to the simple and deterministic code structure, unlike the conventional sparse superposition codes, orthogonal index superposition coding is expressed using a dictionary matrix defined by [Equation 16].

(107) $\begin{array}{cc}𝒸=\left[I_N{I}_N\mathrm{.Math.}{I}_N\right]\left[\begin{array}{c}{x}_1\\ x_2\\ \mathrm{.Math.}\\ x_L\end{array}\right]& \left[\mathrm{Equation}16\right]\end{array}$

(108) When using orthogonal sparse superposition codes, a sense matrix should be carefully selected to ensure the decoding possibilities. By selecting elements of the sense matrix from Gaussian to ensure the restricted isometry property (RIP), decoding is possible with high probability detection. However, orthogonal superposition coding according to embodiments of the inventive concept may guarantee decoding possibility without any probability factor.

(109) Without losing generality, an orthogonal index superposition code may be generated as shown in [Equation 17] by concatenating a single matrix U L times.

(110) 0$\begin{array}{cc}𝒸=\left[UU\mathrm{.Math.}U\right]\left[\begin{array}{c}{x}_1\\ x_2\\ \mathrm{.Math.}\\ x_L\end{array}\right]& \left[\mathrm{Equation}17\right]\end{array}$

(111) With respect to joint information mapping, a method of individually mapping information bits to L subvectors for may be provided. However, this information mapping may be performed jointly. For ease of expression, when [||, ||, . . . , |.sub.L|,]=[N, N−K, . . . , N−(L−1)K,] and .sub.,j=A are assumed, it is possible to generate the same number of possible codewords as that of [Equation 18].

(112) $\begin{array}{cc}\underset{\ell =1}{\overset{L}{.Math.}}\left(\begin{array}{c}N-\left(\ell -1\right)K\\ K\end{array}\right)A^K& \left[\mathrm{Equation}18\right]\end{array}$

(113) Therefore, the code rate may be increased as shown in [Equation 19].

(114) $\begin{array}{cc}R=\frac{.Math.{\log }_2\left(\underset{\ell =1}{\overset{L}{.Math.}}\left(\begin{array}{c}N-\left(\ell -1\right)K\\ K\end{array}\right)A^K\right).Math.}{N}& \left[\mathrm{Equation}19\right]\end{array}$

(115) When the difference from the permutation modulation code is considered, one interesting connection is that the classical permutation modulation code is a special case of an orthogonal index superposition code with joint information bit mapping technique. Specifically, it is possible to generate the same codebook with a modified codebook with joint mapping by setting a signal level set to a singleton ={.sub.,1} for which achieves the speed of

(116) $R=\frac{.Math.{\log }_2\left(\underset{\ell =1}{\overset{L}{.Math.}}\left(\begin{array}{c}N-\left(\ell -1\right)K\\ K\end{array}\right)A^K\right).Math.}{N}.$
Due to the degree of freedom for designing a signal level per subcodeword and the additional information bit mapping of non-zero elements, the encoding method according to embodiments of the inventive concept may generate more codewords for given M and K. In addition, since the superposition encoding method for a plurality of subcodewords reduces the encoding complexity due to a separate bit mapping technique, it is easy to actually implement the encoding apparatus 100.

(117) Looking at the difference from index modulation, the coding scheme according to embodiments of the inventive concept may also generalize the existing index modulation method. Single-layer encoding, that is, L=1 is assumed. This method is the same as index modulation. Accordingly, the coding scheme according to embodiments of the inventive concept may be interpreted as a multiplexing method of multi-layered index modulated signals in an orthogonal manner.

(118) FIG. 6 is a flowchart for describing an encoding method for an orthogonal sparse superposition code according to another embodiment of the inventive concept.

(119) The encoding apparatus 100 may receive binary bits and select an index from a set of binary signals .sub.1 (S101). Here, the support set .sub.1 may be .sub.1={2, 4}.

(120) The encoding apparatus 100 may allocate symbols 1 or 2 to the elements of a selected index set (S102) and generate a subcodeword 1, and .sub.1={1, 2}.

(121) Meanwhile, the encoding apparatus 100 may receive binary bits and select an index for a set of binary signals M.sub.2 (S103). In this case, the set of is =.sub.1\.sub.1 and the remaining indices except the support set .sub.1 are included. Here, the support set .sub.2 is .sub.2={1, 7}.

(122) The encoding apparatus 100 may allocate symbols −1 or −2 to elements in the selected index set (S104), and generate a subcodeword 2, and ={−1, −2}.

(123) Further, the encoding apparatus 100 may generate a transmission codeword by superposing the generated subcodeword 1 and subcodeword 2 (S105).

(124) FIG. 7 is a diagram illustrating an operation of an encoding apparatus for an orthogonal sparse superposition code according to another embodiment of the inventive concept.

(125) Compared with FIG. 5, the encoding apparatus 100 for an orthogonal sparse superposition code according to another embodiment of the inventive concept may further include an encoder. The encoding apparatus 100 may receive interleaved u information bits and generates a codeword “c” through the encoder. u and c satisfy u∈.sub.2.sup.k, c∈.sub.2.sup.n. Here, a code rate is

(126) $r=\frac{k}{n}.$

(127) Thereafter, the encoding apparatus 100 may perform a successive modulation operation in which information is superposed onto L layers without interference with each other, like FIG. 5. The encoding apparatus 100 may successively map c codewords to L different subcodewords.

(128) FIG. 8 is a diagram showing a successive encoding operation using precoding according to another embodiment of the inventive concept.

(129) A near-orthogonal matrix U.sub.j may have N.sub.j columns. U.sub.j may be U.sub.j=[u.sub.j,1, u.sub.j,2, . . . , u.sub.j,N.sub.j] and satisfy U.sub.j.sup.HU.sub.j=I+E.

(130) Referring to the example shown in FIG. 8, there are a matrix U.sub.1 having log.sub.2

(131) $\left(\left(\begin{array}{c}{N}_1\\ 1\end{array}\right)\right)\hspace{1em}$
bits, a matrix U.sub.2 having log.sub.2

(132) $\left(\left(\begin{array}{c}.Math.{𝒩}_2.Math.\\ 1\end{array}\right)\right)\hspace{1em}$
bits, and a matrix U.sub.3 having

(133) ${\log }_2\left(\left(\begin{array}{c}.Math.{𝒩}_3.Math.\\ 1\end{array}\right)\right)\mathrm{bits}.$

(134) The encoding apparatus 100 may select a sixth column from the matrix U.sub.1 having N.sub.1 columns. Here .sub.1=[N.sub.1] in the matrix U.sub.1, and the support set is .sub.1={6}. In addition, the encoding apparatus 100 may generate a projection matrix P.sub.1. The projection matrix P.sub.1 is

(135) $P_1=I-\frac{u_{1,6}{u}_{1,6}^H}{u_{1,6}^H{u}_{1,6}}.$

(136) When the sixth column is selected from the matrix U.sub.1, the encoding apparatus 100 may use a corresponding index when energy is less than or equal to a preset delta as in ={j|∥P.sub.1u.sub.j,2∥.sub.2≤δ}, j∈[N.sub.2] in a case where the generated projection matrix P.sub.1 is projected. Here, when the energy is less than or equal to the delta, ={1, 2, 4, 8} in the matrix U.sub.2. The degree of superposition interference may be controlled by adjusting the delta value. When the eighth column is selected, the support set is .sub.2={8} and A.sub.2=[u.sub.1,6, u.sub.2,8]. In addition, the encoding apparatus 100 may generate a projection matrix P.sub.2. The projection matrix P.sub.2 is P.sub.2=I−A.sub.2(A.sub.2.sup.HA.sub.2).sup.−1A.sub.2.sup.H.

(137) When the eighth column is selected from the matrix U.sub.2, the encoding apparatus 100 may use a corresponding index when the energy is less than or equal to the delta as in ={j|∥P.sub.2u.sub.3,j∥.sub.2≤δ}, j∈[N.sub.3] in a case where the generated projection matrix P.sub.2 is projected. Here, when the energy is less than or equal to the delta, ={2, 7} in the matrix U.sub.3. When the second column is selected, the support set is .sub.3={2}.

(138) As described above, the successive encoding operation using precoding represents a method of superimposing and transmitting information while allowing partial interference in three layers for x1, x2 and x3 as in x=u.sub.1,6+u.sub.2,8+u.sub.3,2.

(139) FIG. 9 is a diagram illustrating an operation of a decoding apparatus for sparse codes according to another embodiment of the inventive concept.

(140) The decoding apparatus 200 for sparse codes according to another embodiment of the inventive concept has a two-stage structure.

(141) First, the decoding apparatus 200 may find K indices having a large size of a reception signal.

(142) In addition, the decoding apparatus 200 may sort the found indices in ascending order (descending order). Here, the indices may be arranged in a pattern promised with a transmitter.

(143) Subsequently, the decoding apparatus 200 may decode small codes using only reception signals carried on the K indices found. The complexity of the decoding apparatus 200 may be linearly associated with a code length. Simplification is achieved by several tens of times compared to conventional decoding apparatuses.

(144) FIGS. 10 and 11 are diagrams illustrating an operation example of a decoding method for sparse codes according to another embodiment of the inventive concept.

(145) As shown in FIG. 10, the decoding apparatus 200 may receive reception signals (S201). Looking at the reception signals, a position where 1 is sent is the fourth position, and a position where −1 is sent is the first position and the seventh position.

(146) The decoding apparatus 200 may sort the reception signals in order of size (S202).

(147) In addition, the decoding apparatus 200 may allocate symbol 1 to an index having the largest received signal sorted in order of size (S203), and detect subcodeword 1 (S204). The support set .sub.1 is .sub.1={4} and .sub.1={1}.

(148) In addition, the decoding apparatus 200 may allocate symbol −1 to the index having the smallest received signal sorted in order of size (S205), and detect subcodeword 2 (S206). The support set .sub.2 is .sub.2={1, 7} and .sub.2={−1}. Thereafter, the decoding apparatus 200 may obtain information contained in each subcodeword detected and position information.

(149) As shown in FIG. 11, the decoding apparatus 200 may receive a reception signal (S301). With respect to the reception signal, positions where 1 or 2 is sent are the second and fourth positions, and positions where −1 or −2 are sent are the first and seventh positions.

(150) The decoding apparatus 200 may sort the reception signals in order of size (S302).

(151) In addition, the decoding apparatus 200 may detect two indices having the largest reception signals sorted in order of size (S303). .sub.1={2, 4} is obtained.

(152) Subsequently, the decoding apparatus 200 may determine whether elements of an estimated index set are symbol 1 or symbol 2, allocate the symbol to the corresponding element (S304), and detect subcodeword 1 (S305). .sub.1={1, 2} is obtained.

(153) In addition, the decoding apparatus 200 may detect two indices having the smallest reception signals sorted in order of size (S306). The support set .sub.1 is .sub.1={2, 4}.

(154) Subsequently, the decoding apparatus 200 may determine whether elements of the estimated index set are symbol 1 or symbol 2 among, allocate the symbol to the corresponding element (S307), and detect subcodeword 1 (S308). .sub.1={1, 2} is obtained. Thereafter, the decoding apparatus 200 may obtain information contained in each subcodeword detected and position information.

(155) FIGS. 12 and 13 are diagrams illustrating an operation of a decoding apparatus for an orthogonal sparse superposition code according to another embodiment of the inventive concept.

(156) As shown in FIG. 12, the decoding apparatus 200 may receive a reception signal (S401), and determine a reception signal that is at a non-zero position in the received reception signal through a support set detector (S402). Here, the decoding apparatus 200 may determine a reception signal that is at the non-zero position by using

(157) $\arg \underset{n\in .Math.N.Math.}{\max }P\left(x_n\in 1_{}.Math.2_{}.Math.y_n\right).$
For example, the decoding apparatus 200 may determine that the first, fourth and seventh indices are not zero.

(158) In addition, the decoding apparatus 200 may identify two sparse subcodes through a MAP layer detector in the case of non-zero positions (S403). That is, the decoding apparatus 200 may determine which subcodeword set is. Here, the decoding apparatus 200 may determine which subcodeword set is by using comparison in size between P(x.sub.n∈.sub.1|y.sub.n, .sub.1∪.sub.2) and P(x.sub.n∈.sub.2|y.sub.n, .sub.1∪.sub.2). For example, the decoding apparatus 200 may identify whether subcodewords correspond to the first and seventh indices or whether a subcodeword corresponds to the fourth index.

(159) Subsequently, the decoding apparatus 200 may detect a subcodeword through a MAP symbol detector (S404). Here, the decoding apparatus 200 may detect a subcodeword using

(160) 0$\arg \underset{a_{1,j}\in {𝒜}_1}{\max }P\left(x_n=a_{1,j}.Math.y_n,1_{}\right),\arg \underset{a_{1,j}\in {𝒜}_2}{\max }P\left(x_n=a_{2,j}.Math.y_n,2_{}\right),\mathrm{.Math.},\arg \underset{a_{L,j}\in {𝒜}_L}{\max }P\left(x_n=a_{L,j}.Math.y_n,L_{}\right).$
For example, the decoding apparatus 200 may obtain information contained in each subcodeword and position information.

(161) FIG. 13 is a diagram for again describing the operation illustrated in FIG. 12 again using a probability formula.

(162) The decoding apparatus 200 may receive reception signals, calculate probability equations P(y.sub.n|x.sub.n∈.sub.1∪.sub.2)P(x.sub.n∈.sub.1∪.sub.2) for all N, and then find an index having a maximum value K.sub.1+K.sub.2 as in

(163) $\begin{array}{cc}\arg \underset{n\in \left[N\right]}{\max }P\left(x_n\in 1_{}.Math.2_{}.Math.y_n\right).& \left(\mathrm{S501}\right)\end{array}$

(164) In addition, when x.sub.n belongs to the union of .sub.1 and .sub.2, the decoding apparatus 200 may find an index set K.sub.1 that maximizes the probability expression P(x.sub.n∈.sub.1|y.sub.n, .sub.1∪.sub.2), P(y.sub.n|x.sub.n, .sub.1∪.sub.2)P(x.sub.n∈.sub.1|x.sub.n∈.sub.1∪.sub.2) (S502). In addition, the decoding apparatus 200 finds an index set K.sub.2 that maximizes the probability equation P(x.sub.n∈.sub.2|y.sub.n, .sub.1∪.sub.2).

(165) In addition, the decoding apparatus 200 may detect a subcodeword through the MAP symbol detection operation using

(166) $\begin{array}{cc}\arg \underset{a_{1,j}\in {𝒜}_1}{\max }P\left(x_n=a_{1,j}.Math.y_n,1_{}\right).& \left(\mathrm{S503}\right)\end{array}$
Also, the decoding apparatus 200 may detect a subcodeword through a MAP symbol detection operation using

(167) $\arg \underset{a_{1,j}\in {𝒜}_2}{\max }P\left(x_n=a_{2,j}.Math.y_n,2_{}\right).$

(168) Meanwhile, in relation to embodiments of the inventive concept, an element-wise maximum a posterior (MAP) decoding with successive support set cancellation (E-MAP-SSC) will be described. Embodiments of the inventive concept provides a low-complexity decoding algorithm, referred to as bit-wise maximum a posterior decoding with successive support set cancellation, with successive support set cancellation.

(169) FIG. 14 is a diagram illustrating an operation of a decoding apparatus for an orthogonal sparse superposition code according to another embodiment of the inventive concept using a probability equation.

(170) As shown in FIG. 14, the main idea of embodiments of the inventive concept is to successively decode subcodeword vectors x.sub.1 at x to maximize a posterior probability (APP) using the Bayesian approach. It is noted that the joint APP is factored by [Equation 20].

(171) $\begin{array}{cc}P\left(x.Math.y\right)=\underset{\ell =1}{\overset{L}{.Math.}}P\left(x_{\ell }.Math.y,x_{\ell -1},.Math.,x_2,x_1\right)& \left[\mathrm{Equation}20\right]\end{array}$

(172) From this decomposition, the decoding algorithm according to the embodiments of the inventive concept is to successively estimate subcodeword vectors. The B-MAP-SSC according to the embodiments of the inventive concept may perform iteration L times. Each iteration includes decoding a subcodeword vector and subtracting the support set of the decoded subcodeword to evolve the prior distribution for the next iteration. Specifically, in the first iteration, the decoding apparatus 200 may perform B-MAP decoding to identify the first support set .sub.1. Since all the reception signals for m∈[M] are independent, the joint APP is factored by [Equation 21].

(173) $\begin{array}{cc}\begin{array}{c}P\left(x.Math.y\right)=\underset{n=1}{\overset{N}{.Math.}}P\left(x_n.Math.y_n\right)\underset{\ell =1}{\overset{L}{.Math.}}{1}_{\left\{\underset{n=1}{\overset{N}{.Math.}}{1}_{\left\{x_n\in 𝒜\right\}}=K_{\ell }\right\}}\\ =\underset{n=1}{\overset{N}{.Math.}}\frac{P\left(y_n.Math.x_n\right)P\left(x_n\right)}{P\left(y_n\right)}\underset{\ell =1}{\overset{L}{.Math.}}{1}_{\left\{\underset{n=1}{\overset{N}{.Math.}}{1}_{\left\{x_n\in 𝒜\right\}}=K_{\ell }\right\}}\end{array}& \left[\mathrm{Equation}21\right]\end{array}$

(174) To calculate [Equation 21], the likelihood function given by [Equation 22] is needed.

(175) $\begin{array}{cc}P\left(y_n.Math.x_n\right)=\frac{1}{\sqrt{2{\mathrm{\pi \sigma }}^2}}\exp \left(-\frac{{.Math.y_n-x_n.Math.}^2}{2{\sigma }^2}\right)& \left[\mathrm{Equation}22\right]\end{array}$

(176) Here, x.sub.n∈{{0}∪{.sub.=1}}. The prior distribution of x is also decomposed into [Equation 23].

(177) $\begin{array}{cc}P\left(x\right)=\frac{1}{Z}\underset{n=1}{\overset{N}{.Math.}}P\left(x_n\right)\underset{\ell =1}{\overset{L}{.Math.}}{1}_{\left\{\underset{n=1}{\overset{N}{.Math.}}{1}_{\left\{x_n\in 𝒜\right\}}=K_{\ell }\right\}}& \left[\mathrm{Equation}23\right]\end{array}$

(178) In [Equation 23], Z∈.sup.+ is the probability distribution constant, and is the indicator function for the set c. K.sub.1, K.sub.2, . . . , K.sub.L non-zero supports are selected uniformly at each .sub.1, , . . . , .sub.L. Also, the non-zero elements of are uniformly selected in for . The probability mass function of x.sub.n may be expressed as in [Equation 24].

(179) $\begin{array}{cc}P\left(x_{\ell ,n}\right)=\{\begin{array}{cc}{x}_{\ell ,n}=0,& w.p.1-\frac{K_{\ell }}{N-\underset{j=1}{\overset{\ell -1}{.Math.}}{K}_j}\\ x_{\ell ,n}\in {𝒜}_{\ell },& w.p.\frac{K_{\ell }}{N-\underset{j=1}{\overset{\ell -1}{.Math.}}{K}_j}\end{array}& \left[\mathrm{Equation}24\right]\end{array}$

(180) Here, [Equation 25] may be obtained by calling the prior distribution .sub.,n in [Equation 24].

(181) $\begin{array}{cc}P\left(y_n\right)=P\left(y_n.Math.x_{\ell ,n}\in {\ell }_{}\right)P\left(x_{\ell ,n}\in {\ell }_{}\right)+P\left(y_n.Math.x_{\ell ,n}.Math.{\ell }_{}\right)P\left(x_{\ell ,n}.Math.{\ell }_{}\right)& \left[\mathrm{Equation}25\right]\end{array}$

(182) Using [Equation 22], [Equation 24], and [Equation 25], the decoding apparatus 200 may perform element-wise MAP support detection, that is, signal set detection, which is calculated by [Equation 26].

(183) 0$\begin{array}{cc}\begin{array}{cc}P\left(y_n\right)=& P\left(y_n.Math.x_{\ell ,n}\in {\ell }_{}\right)P\left(x_{\ell ,n}\in {\ell }_{}\right)+\\ \text{}& P\left(y_n.Math.x_{\ell ,n}.Math.{\ell }_{}\right)P\left(x_{\ell ,n}.Math.{\ell }_{}\right)\\ =& \frac{1}{\sqrt{2{\mathrm{\pi \sigma }}^2}}\underset{j=1}{\overset{.Math.{\ell }_{}.Math.}{.Math.}}{e}^{-\frac{{.Math.y_n-x_{\ell ,j}.Math.}^2}{2{\sigma }^2}}\frac{K_{\ell }}{N-\underset{j=1}{\overset{\ell -1}{.Math.}}{K}_j}\frac{1}{.Math.{\ell }_{}.Math.}+\\ \text{}& \frac{1}{\sqrt{2{\mathrm{\pi \sigma }}^2}}{e}^{-\frac{{.Math.y_n.Math.}^2}{2{\sigma }^2}}\left(1-\frac{K_{\ell }}{N-\underset{j=1}{\overset{\ell -1}{.Math.}}{K}_j}\right)\end{array}& \left[\mathrm{Equation}26\right]\end{array}$

(184) In addition, the decoding apparatus 200 may estimate the support set of using a reclusive algorithm. To describe the process of the reclusive algorithm in detail, it is assumed that the support set of is estimated in the -th iteration step. In this case, the set of support sets estimated through the algorithm up to the previous step −1 is expressed by .sub.1, . . . , . Using the support set information .sub.1, . . . , obtained in the previous step, in the th step, is identified through MAP decoding.

(185) Then, the decoding apparatus 200 may have information of

(186) ${\widehat{𝒩}}_{\ell }=\left[N\right]\backslash \stackrel{\ell -1}{\underset{j=1}{.Math.}}{\widehat{ℐ}}_j.$
Using this information, the decoding apparatus 200 may calculate the APP as in [Equation 27].

(187) $\begin{array}{cc}P\left(x_{\ell }.Math.y,1_{},.Math.,{\ell -1}_{}\right)=\underset{n\in {\widehat{𝒩}}_{\ell }}{\Pi }\frac{P\left(y_n.Math.x_{\ell ,n}\right)P\left(x_{\ell ,n}\right)}{P\left(y_n\right)}{1}_{\left\{{\Sigma }_{n\in {\widehat{𝒩}}_{\ell }}{1}_{\left\{x_{\ell ,n}\in {𝒜}_{\ell }\right\}}=K_{\ell }\right\}}& \left[\mathrm{Equation}27\right]\end{array}$

(188) In order to calculate [Equation 27], the information of [Equation 28] is needed.

(189) $\begin{array}{cc}P\left(y_n.Math.x_{\ell ,n}\in {\ell }_{}\right)=\frac{1}{.Math.{\ell }_{}.Math.}\underset{j=1}{\overset{.Math.{\ell }_{}.Math.}{.Math.}}\frac{1}{\sqrt{2{\mathrm{\pi \sigma }}^2}}\exp \left(-\frac{{.Math.y_n-a_{\ell ,j}.Math.}^2}{2{\sigma }^2}\right)& \left[\mathrm{Equation}28\right]\end{array}$

(190) In addition, the probability information for is decomposed as in [Equation 29]

(191) $\begin{array}{cc}P\left(x_{\ell }\right)=\frac{1}{Z}\underset{n\in {\widehat{𝒩}}_{\ell }}{\Pi }P\left(x_{\ell ,n}\right)1_{\left\{{\Sigma }_{n\in {\widehat{𝒩}}_{\ell }{1}_{\left\{x_{\ell ,n}\in {𝒜}_{\ell }\right\}}=K_{\ell }}\right\}}& \left[\mathrm{Equation}29\right]\end{array}$

(192) Finally, by combining [Equation 24], [Equation 26], and [Equation 24], the decoding apparatus 200 may calculate a probability value for the support set by [Equation 30].

(193) $\begin{array}{cc}P\left(n\in {\ell }_{}.Math.y_n\right)=\frac{P\left(y_n.Math.x_{\ell ,n}\in \right)P\left(x_{\ell ,n}\in \right)}{P\left(y_n\right)}& \left[\mathrm{Equation}30\right]\end{array}$

(194) Thereafter, the decoding apparatus 200 may estimate the support set of in the -th iteration as the largest ={.sub.,1, .sub.,2, . . . , , } using [Equation 31].

(195) $\begin{array}{cc}P\left({\hat{i}}_{\ell ,1}\in {ℐ}_{\ell }|y_{\ell ,1}\right)>P\left({\hat{i}}_{\ell ,2}{ℐ}_{\ell }|y_{\ell ,2}\right),.Math.& \left[\mathrm{Equation}31\right]\end{array}$

(196) The decoding apparatus 200 may estimate a signal level of .sub.,n using [Equation 32].

(197) $\begin{array}{cc}\begin{array}{c}{x}_{\ell ,n}=\arg \underset{a_{\ell ,j}\in {𝒜}_{\ell }}{\max }P\left(x_{\ell ,n}=x_{\ell ,j}|y_n,x_n\in {\widehat{ℐ}}_{\ell }\right)\\ =\arg \underset{a_{\ell ,j}\in {𝒜}_{\ell }}{\min }{.Math.y_n-a_{\ell ,j}.Math.}^2\end{array}& \left[\mathrm{Equation}32\right]\end{array}$

(198) For the computational complexity, the most salient aspect of the embodiments of the inventive concept is that it has a linear complexity with simplicity at a block length N as shown in FIG. 14. In more detail, the inventive concept may identify an estimated support set by selecting the largest value among values of the posterior probability (APP) of N−K.sub.j after calculating N−K.sub.j for each element as described above. Therefore, a complexity of identifying the estimated support set can be calculated as ((N−K.sub.j) log()). When the estimated support set is identified, the decoding apparatus may perform detection of the maximum likelihood signal level for one layer (1-th layer) through the calculation of ||. Therefore, the resulting total decoding complexity can be expressed as (N−K.sub.j) log()+||, and, under premise of N>> for ∈[L], the number of layers and the block length may all have a linear complexity of (LN).

(199) FIG. 15 is a diagram illustrating an operation of a decoding apparatus for an orthogonal sparse superposition code according to still another embodiment of the inventive concept using a probability equation.

(200) In addition, in order to further lower the complexity of E-MAP-SSC decoding, as shown in FIG. 15, the inventive concept may detect a support set at a non-zero position in a reception signal and identify a set of subcodewords from the detected support set. In this case, the decoding apparatus may apply the E-MAP-SSC to two-layered OSS codes using K.sub.1, K.sub.2, .sub.1={1}, and .sub.2={−1}. This method may be an embodiment of the decoding method described with reference to FIG. 11.

(201) In more detail, the decoding apparatus may take an absolute value of the reception signal, detect the support set that is at the non-zero position in the descending order of absolute values, and perform the E-MAP-SSC on the detected support set. In this case, the E-MAP-SSC may operate in the same way as a simple ordered statistics decoder. For example, when the posterior probability of n∈.sub.1 is calculated, [Equation 34] can be derived through [Equation 33].

(202) $\begin{array}{cc}P\left(y_n|n\in {ℐ}_1\right)=\exp \left(-\frac{{\left(y_n-1\right)}^2}{2{\sigma }^2}\right),P\left(y_n|n.Math.{ℐ}_1\right)=\frac{\left(N-K_1\right)\exp \left(-\frac{y_n^2}{2{\sigma }^2}\right)+K_1\exp \left(-\frac{{y_n+1)}^2}{2{\sigma }^2}\right)}{N-2K_1},P\left(n\in {ℐ}_1\right)=\frac{K_1}{N},\mathrm{and}P\left(n.Math.{ℐ}_1\right)=\frac{N-2K_1}{N}& \left[\mathrm{Equation}33\right]\end{array}$$\begin{array}{cc}P\left(n.Math.{ℐ}_1|y_n\right)=\frac{1}{1+\exp \left(-\frac{2y_n}{{\sigma }^2}\right)+\frac{\left(N-2K_1\right)}{K_1}\exp \left(-\frac{2y_n-1}{2{\sigma }^2}\right)}.& \left[\mathrm{Equation}34\right]\end{array}$

(203) Since P(n∈.sub.1|) is a monotonically increasing function of , the index set .sub.1 may be determined by the largest value K.sub.1 of .sub.1. Likewise, K.sub.1 may be determined by the smallest value K.sub.2 of .

(204) FIG. 16 is a diagram showing a parallel decoding structure using precoding according to another embodiment of the inventive concept.

(205) As shown in FIG. 16, a transmission signal x generated through a successive encoding structure using precoding shown in FIG. 8 is received as a reception signal y through a channel. Here, x=u.sub.1,6+u.sub.2,8+u.sub.3,2 and y=u.sub.1,6+u.sub.2,8+u.sub.3,2+v.

(206) The decoding apparatus 200 may detect a subcodeword x.sub.1 from the reception signal y using a matrix U.sub.1.sup.H.

(207) Further, the decoding apparatus 200 may obtain u.sub.1,6 information bits corresponding to the subcodeword x.sub.1, and detect a subcodeword x.sub.2 using a matrix U.sub.2.sup.H from a signal from which u.sub.1,6 information bits are removed from the reception signal y.

(208) Further, the decoding apparatus 200 may obtain u.sub.2,8 information bits corresponding to the subcodeword x.sub.2, and detect a subcodeword using a matrix U.sub.3.sup.H from a signal from which u.sub.1,6 information bits and u.sub.2,8 information bits are removed from the reception signal y.

(209) FIG. 17 is a block diagram for describing configurations of an encoding apparatus and a decoding apparatus according to an embodiment of the inventive concept.

(210) An embodiment of the inventive concept relates to a new class of sparse codes and orthogonal sparse superposition codes for efficiently transmitting a short information message having a small block length (e.g., less than several hundreds of bits) less than a preset size in a Gaussian channel. Orthogonal sparse superposition code, called orthogonal index superposition code is to map information bits into multiple index-modulated subcodewords in such a way that non-zero support sets of subcodewords are mutually exclusive. By taking a specific type of linear combination of these index-modulated vectors, the encoding apparatus 100 may generate an orthogonal index superposition codeword. The class of codes according to an embodiment of the inventive concept may generalize conventional classical permutation modulation codes and a recently introduced index modulation technique.

(211) In addition, according to another embodiment of the inventive concept, a bit-wise maximum a posterior decoding with successive index cancellation (B-MAP-SIC) decoding apparatus is provided. This B-MAP-SIC decoding apparatus may have linear complexity with a block length while achieving near-optimal decoding performance. By simulation, the encoding apparatus 100 and the decoding apparatus 200 according to the embodiments of the inventive concept may outperform the classical convolutional codes using Viterbi decoding and polar codes with list decoding, especially when the code block size is less than several hundreds of bits.

(212) As shown in FIG. 17, the encoding apparatus 100 according to an embodiment of the inventive concept may include an encoder 110, a memory 120, and a processor 130. In addition, the decoding apparatus 200 according to an embodiment of the inventive concept may include a decoder 210, a memory 220, and a processor 230. However, not all of the illustrated components are essential components. The encoding apparatus 100 and the decoding apparatus 200 may be implemented by more components than the illustrated components, and the encoding apparatus 100 and the decoding apparatus 200 may be implemented by fewer components than the illustrated components.

(213) Hereinafter, configurations of the encoding apparatus 100 and the decoding apparatus 200 will be described sequentially.

(214) In the encoding apparatus 100, the encoder 110 may generate bits coded using information bits, that is, a message, that is, codewords.

(215) The memory 120 may store one or more programs associated with encoding of sparse codes and orthogonal sparse superposition codes.

(216) The processor 130 may be connected to the encoder 110 and the memory 120 and may execute one or more programs stored in the memory 120. According to embodiments for sparse codes, the processor 130 may select an index set that is a part of a code block using information bits, and map codewords less than a preset size into the selected index set.

(217) According to embodiments, the processor 130 may select a plurality of code positions using the information bits. The processor 130 may map a codeword less than a preset size to the union or subset of the selected index sets.

(218) According to embodiments for orthogonal sparse superposition codes, the processor 130 may select an index set from code blocks by using the information bits in a process of successively encoding information bits in a plurality of layers. In this case, the processor 130 may select the next index set sequentially from the remaining code blocks except the previous index set that has been used in a previous layer, sequentially generate a plurality of subcodewords by allocating modulation symbols to an index set selected in each layer, and generate sparse superposition codes by combining the generated plurality of subcodewords.

(219) According to embodiments, when sequentially generating a plurality of subcodewords, the next subcodeword may maintain orthogonality with the previous subcodeword. When a plurality of subcodewords are sequentially generated, the next subcodeword may maintain near orthogonality to the previous subcodeword. The processor 130 may generate a projection matrix corresponding to the previous index set used in the previous layer, and when energy is less than a preset delta in a case where the generated projection matrix is projected, use the corresponding index as the next index set. The processor 130 may control the degree of superposition interference by adjusting the delta value. The processor 130 may sequentially select an index set for each section in a code block which is previously divided into a plurality of sections in successively encoding information bits in a plurality of layers.

(220) Meanwhile, in the decoding apparatus 200, the decoder 210 may obtain the decoded information bits by performing decoding on the detected codewords.

(221) The memory 220 may store one or more programs related to the decoding of the sparse codes.

(222) The processor 230 may be connected to the decoder 210 and the memory 220 and may execute one or more programs stored in the memory 220. According to embodiments for sparse codes, the processor 230 may sort the reception signals in the order of size, detect a preset number of uppermost or lowermost index sets from the reception signals sorted in the order of size, and perform decoding on sparse codes using the reception signals carried on the detected index sets.

(223) According to embodiments, the processor 230 may detect subcodewords by allocating modulation symbols corresponding to elements of the detected index set. The processor 230 may determine modulation symbols corresponding to elements of the detected index set, and detect subcodewords by allocating determined modulation symbols.

(224) According to embodiments for orthogonal sparse superposition codes, the processor 230 may detect a support set at a non-zero position in a reception signal, identify a set of subcodewords from the detected support set, and perform decoding of the identified set of subcodewords.

(225) According to embodiments, the processor 230 may identify a set of subcodewords through comparison in size of probabilities belonging to index sets, respectively. The processor 230 may determine modulation symbols corresponding to elements of the identified set of subcodewords, and detect subcodewords by allocating the determined modulation symbols. The processor 230 may sequentially detect a support set that is at a non-zero position in the reception signal which is divided into a plurality of sections in advance. The processor 230 may sequentially detect a next support set at a non-zero position in the remaining reception signals except the previous support set used in the previous section.

(226) FIG. 18 is a diagram showing results of comparison between an embodiment of the inventive concept and a conventional code when a code length is 32.

(227) In FIG. 18, when a code length of 32, there is shown comparison in performance between convolutional codes 1/2 [32, 16] and polar codes 1/2 [32, 16] which are conventional codes and an embodiment of the inventive concept (OSS code). The block error rate (BLER) of the embodiment of the inventive concept (OSS code) is similar to that of the polar code.

(228) TABLE-US-00001 TABLE 1 Present Invention (OSS) Polar code Conv. code M log (2) List × Mlog(M) 64 × M

(229) When comparing code complexities, the embodiment (OSS) of the inventive concept may find out the two largest values, M*log(2), whereas the polar codes are List*Mlog(M), and the convolution codes has a code length (M) of “Soft Viterbi decoder=# of states×code length (M)=64×32.”

(230) As described above, the embodiment of the inventive concept may achieve a block error rate similar to that of polar codes, which is known near-optimal codes at a small length known in the art, while reducing the complexity by 5 to 80 times.

(231) FIGS. 19 to 21 are diagrams showing results of comparison between an embodiment of the inventive concept and conventional codes when code lengths are 64, 128 and 256, respectively.

(232) Referring to FIGS. 19 to 21, in the case of simulation, an embodiment (OSS code) of the inventive concept outperforms block error rates of classic convolutional codes using Viterbi decoding and polar codes having list decoding when a code block size is less than several hundreds of bits.

(233) Meanwhile, there may be provided a non-transitory computer-readable storage medium for storing instructions that cause, when executed by a processor, the processor to execute a method including selecting index sets that are a part of code blocks using information bits, and mapping codewords less than a preset size to the selected index sets.

(234) Further, there may be provided a non-transitory computer-readable storage medium for storing instructions that cause, when executed by a processor, the processor to execute a method including selecting an index set from code blocks using information bits in successively encoding the information bits in a plurality of layers and sequentially selecting a next index set from remaining code blocks except a previous index set used in a previous layer, sequentially generating a plurality of subcodewords by allocating modulation symbols to index sets selected by the layers respectively, and generating sparse superposition codes by combining the generated plurality of subcodewords.

(235) As described above, in the case where the code block length is a finite length, the inventive concept may represent the BLER as in [Equation 35] for a single layered OSS code having a rate of

(236) $R=\frac{.Math.{\log }_2\left(\left(\begin{array}{c}N\\ K_1\end{array}\right)\right).Math.}{N}.$

(237) 0$\begin{array}{cc}P\left(\epsilon \right)=1-\frac{\left(N-K_1\right)}{\sqrt{2{\mathrm{\pi \sigma }}^2}}{\int }_{-\infty }^{\infty }{Q\left(\frac{y-1}{\sigma }\right)}^{K_1}{\left\{1-Q|\left(\frac{y}{\sigma }\right)\right\}}^{N-K_1-1}{e}^{-\frac{y^2}{2{\sigma }^2}}\mathrm{dy},\mathrm{where}Q\left(x\right)={\int }_x^{\infty }\frac{1}{\sqrt{2x}}{e}^{-\frac{x^2}{2}}\mathrm{du}& \left[\mathrm{Equation}35\right]\end{array}$

(238) In addition, the inventive concept may provide a tight upper bound for a two-layered OSS code. For example, for a two-layered OSS code with a rate of

(239) $R=\frac{.Math.{\log }_2\left(\left(\begin{array}{c}N\\ K\end{array}\right)\right).Math.+.Math.{\log }_2\left(\left(\begin{array}{c}N-K\\ K\end{array}\right)\right).Math.}{N},$
the BLER may have a tight upper bound such as [Equation 36].

(240) $\begin{array}{cc}P\left(\epsilon \right)\le 1-{\left(1-Q\left(\frac{1}{\sigma }\right)\right)}^{2K}\frac{\left(N-2K\right)}{\sqrt{2{\mathrm{\pi \sigma }}^2}}{\int }_0^{\infty }{Q_{\frac{1}{2}}\left(\frac{1}{\sigma },\frac{\sqrt{y}}{\sigma }\right)}^{2K}{\left\{1-2Q\left(\frac{\sqrt{y}}{\sigma }\right)\right\}}^{N-2K-1}{y}^{-\frac{1}{2}}{e}^{-\frac{y}{{\sigma }^2}}\mathrm{dy},\mathrm{where}{Q}_M\left(a,b\right)\mathrm{denotes}\mathrm{the}\mathrm{generalized}\mathrm{Marcum}Q‐\mathrm{function}\mathrm{of}\mathrm{order}M& \left[\mathrm{Equation}36\right]\end{array}$

(241) As described above, the inventive concept may analyze code error performance in a certain code length in an analytical form. In a communication system that requires high reliability while transmitting short packets such as IoT, the minimum Eb/N0 required to achieve the performance of BLER 10-9 needs to be calculated. Accordingly, the inventive concept capable of predicting code error performance in an analytical form without relying on experimental results may meet the needs of recent communication systems.

(242) In addition, the inventive concept, which is a single layered OSS code of

(243) $R=\frac{{\log }_2\left(\left(\begin{array}{c}N\\ K\end{array}\right)\right)}{N},$
may achieve the Shannon limit of the power-limited regime with linear decoding complexity when a code block length is infinite.

(244) In addition, the feature of the inventive concept is to obtain a coding gain such as a bi-orthogonal coded known as a code capable of achieving the Shannon limit in a power-limited regime. As an example, since the OSS code of the inventive concept is

(245) $d_{\min }^2\left(C\right)=2,E_s=\frac{1}{N},\mathrm{and}R=\frac{{\log }_{2}N}{N},$
under the assumption of the length is N and the single-layered orthogonal sparse superposition code is K.sub.1=1, the nominal coding gain may be calculated as [Equation 37].

(246) $\begin{array}{cc}{\gamma }_c^{\mathrm{oss}}=\frac{d_{\min }^2\left(C\right)/4}{E_s/R}=\frac{{\log }_{2}N}{2}& \left[\mathrm{Equation}37\right]\end{array}$

(247) Since the normalized number of the nearest neighbors per bit is

(248) $\frac{N-1}{{\log }_{2}N},$
the effective coding gain of the code of the inventive concept is expressed as in [Equation 38].

(249) $\begin{array}{cc}{\gamma }_{\mathrm{eff}}^{\mathrm{oss}}=10{\log }_{10}\left(\frac{{\log }_{2}N}{2}\right)-0.2{\log }_2\left(\frac{N-1}{{\log }_{2}N}\right)\mathrm{dB}.& \left[\mathrm{Equation}38\right]\end{array}$

(250) As described above, the inventive concept not only obtains a coding gain such as bi-orthogonal coded, but also achieve a complexity of O(N) which is a complexity much less than O(NlogN) (assuming a code length of N) that is the complexity of the optimal low-complexity decoding (Hadamard transform decoding) of a bi-orthogonal code (also referred to as 1st-order Reed-Muller code).

(251) FIG. 22 is a diagram showing a result of comparison between an embodiment of the inventive concept and a conventional code when a block length increases while lowering a code rate.

(252) Referring to the drawing, the BLER between the OSS code of the inventive concept using the E-MAP-SSC and the 1/2-polar code using the SC decoder may be compared for different block lengths as shown in the drawing.

(253) The inventive concept exhibits better performance than polar codes at block lengths of 128, 256, and 512, and decoding complexity is also less complex than polar codes.

(254) FIG. 23 is a diagram showing analysis of BLER for a single layered orthogonal sparse superposition code, FIG. 24 is a diagram showing analysis of BLER for a two-layered orthogonal sparse superposition code, and FIG. 25 is a diagram showing a result of comparison between an embodiment of the inventive concept and a conventional code when a code length is 256.

(255) Referring to the drawings, the inventive concept using the OSS code may obtain a large coding gain due to linear decoding complexity, compared to a low-rate code (repetition code+convolution code; polar code) used in an existing LTE control channel, when comparing performance with an existing code in terms of SNR per bit (e.g., E.sub.b/N.sub.0).

(256) Meanwhile, according to an embodiment of the inventive concept, the various embodiments described above may be implemented as software including instructions stored in a machine-readable storage media. The machine may be a device capable of calling a stored instruction from a storage medium and operating in accordance with the called instruction, and may include an electronic device (e.g., the electronic device A) according to the disclosed embodiments. The instructions, when executed by a processor, may cause the processor to perform a function corresponding to the instruction directly or using other components under the control of the processor. The instruction may include codes generated or executed by a compiler or interpreter. The machine-readable storage medium may be provided in the form of a non-transitory storage medium. Here ‘non-temporary’ means that the storage medium does not include a signal and is tangible, and does not distinguish whether data is stored semi-permanently or temporarily on the storage medium.

(257) Further, according to an embodiment of the inventive concept, the method according to the various embodiments described above may be included in a computer program product and provided. The computer program product may be traded between a seller and a buyer as a product. The computer program product may be distributed online in the form of a machine-readable storage medium (e.g., compact disc read only memory (CD-ROM)) or through an application store (e.g., Play Store™). In the case of online distribution, at least a part of the computer program product may be temporarily generated or at least temporarily stored in a storage medium, such as a memory of a manufacturer's server, an application store's server, or a relay server.

(258) Also, various embodiments described herein may be embodied in a computer or similar device-readable recording medium using software, hardware, or a combination thereof. In some cases, the embodiments described herein may be implemented by a processor itself. According to software implementation, embodiments such as procedures and functions described herein may be implemented as separate software modules. Each of the software modules may perform one or more functions and operations described herein.

(259) Meanwhile, computer instructions for performing a processing operation of a device according to the various embodiments described above may be stored in a non-transitory computer-readable medium. The computer instructions stored in the non-transitory computer-readable medium cause, when executed by a processor of a specific device, the specific device to perform processing operations in the device according to the various embodiments described above. The non-transitory computer readable-medium refers to a medium that stores data semi-permanently rather than a medium storing data for a very short time, such as a register, a cache, and a memory, and is readable by an apparatus. Specific examples of the non-transitory computer-readable media may include CD, DVD, hard disk, Blu-ray disk, USB, memory card, ROM, and the like.

(260) Further, each component (e.g., a module or a program) according to various embodiments described above may be composed of single entity or a plurality of entities, a part of the above-described sub-components may be omitted, or other sub-components may be further included in various embodiments. Alternatively or additionally, some components (e.g., modules or programs) may be integrated into one entity to perform the same or similar functions performed by the components prior to integration. Operations performed by a module, a program, or other components according to various embodiments may be executed sequentially, in parallel, repeatedly, or in a heuristic method. In addition, some operations may be executed in different sequences or may be omitted. Alternatively, other operations may be added.

(261) While the present disclosure has been shown and described with reference to various embodiments thereof, the inventive concept is not limited to the specific embodiments described above. Various modifications can be implemented by those of ordinary skill in the technical field belonging to the present disclosure without departing from the gist of the inventive concept claimed in the claims, and these modifications should not be individually understood from the technical idea or perspective of the inventive concept.

(262) The disclosed technology may have the following effects. However, since a specific embodiment does not mean to include all of the following effects or only the following effects, it should not be understood that the scope of the disclosed technology is limited by this.

(263) Embodiments of the inventive concept may simultaneously obtain a coding gain and a power gain in a short block length.

(264) Embodiments of the inventive concept may increase the power gain by providing sparse codes and orthogonal sparse superposition codes in which most of transmission codewords are zero and a non-zero portion is small.

(265) Embodiments of the inventive concept may increase the coding gain by using maximum distance separable (MDS) codes having a large coding gain in the non-zero portion or by using a certain conventional code.

(266) Although the embodiments of the inventive concept have been described for short-length codes, the decoding method according to the embodiments of the inventive concept may achieve linear decoding complexity in the block lengths even for a very long block length, and be very useful for THz communication systems (a large number of received samples and power-limited regime).

(267) While the inventive concept has been described with reference to exemplary embodiments, it will be apparent to those skilled in the art that various changes and modifications may be made without departing from the spirit and scope of the inventive concept. Therefore, it should be understood that the above embodiments are not limiting, but illustrative.