# US 10,484,133 B2 · Methods and systems for decoding a data signal based on the generation of a decoding tree

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,484,133 B2
- Document ID: US10484133B2
- Status: Granted
- Kind: B2
- Application number: 15/514,576
- Filed: 2015-09-28
- Published: 2017-09-14
- Granted: 2019-11-19
- Earliest claimed: 2014-09-29
- Assignees: Institut Mines-Telecom
- Applicants: Institut Mines Telecom
- Inventors: Asma Mejri; Ghaya Rekaya-Ben Othman
- Web page: https://patentgrep.com/patent/US10484133B2

## CPC

- H04L 1/0052: {Realisations of complexity reduction techniques, e.g. pipelining or use of look-up tables}
- H04L 1/0054: {Maximum-likelihood or sequential decoding, e.g. Viterbi, Fano, ZJ algorithms}
- H04L 25/03197: {methods of calculation involving metrics}
- H04L 25/03203: {Trellis search techniques}
- H04L 25/03891: {Spatial equalizers (MIMO diversity systems H04B7/0413)}
- H04L 27/38: Demodulator circuits; Receiver circuits
- H04L 2025/03426: {transmission using multiple-input and multiple-output channels}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A decoder or a decoding method for decoding a data signal is provided by iteratively constructing a decoding tree comprising nodes, each representing a component of a symbol of a data signal, each iteration comprising, for a current node of the tree stored in the top of the stack; generating a reference child node of the current node from the data signal; from the reference child node, generating a first and second neighbor child nodes by subtracting/adding a positive integer parameter from/to the value of the reference node; storing in the stack three child nodes derived from the reference, first and second neighbor child nodes, the nodes stored in the stack being ordered by increasing values of a node metric; removing the current node stack; selecting the top node of the stack as the new current node. The data signal is estimated from the stack node information.

## Claims

### Claim 1

A method of decoding a received data signal in a communication system, wherein said method comprises:
iteratively constructing a decoding tree, each node of said decoding tree corresponding to a component of a symbol of said data signal, and being associated with a metric,
wherein said step of iteratively constructing the decoding tree implements at least one iteration of the following steps, for a current node of the tree stored in the top of a stack:
generating a reference child node (si) of said current node from said vector representing the received data signal,
from the reference child node (si), generating a first neighbor child node by subtracting a positive integer parameter (p) from the value of the reference node (si), and a second neighbor child node by adding said positive integer parameter (p) to the value of the reference child node (si);
storing in said stack at most three child nodes among the reference child node and said first and second neighbor child nodes, each child node being stored in the stack in association with node information comprising a predetermined metric, the nodes in the stack being ordered by increasing values of metrics;
removing the current node from said stack;
selecting the top node of said stack as the new current node;
wherein the value of each node in the tree corresponds to the component of a symbol belonging to a given constellation having a predefined range between a minimum threshold and a maximum threshold, each step of generating a child node comprising setting the value of the child node based on said maximum and minimum thresholds wherein said method further comprises determining an estimation of said data signal from the node information stored in said stack.

### Claim 2 (depends on 1)

The method of claim 1, wherein said received data signal corresponds to a transmitted data signal transported by a transmission channel, said transmission channel being associated with a channel matrix (H) of a given dimension (n) and a QR decomposition being previously applied to said channel matrix where Q designates an orthogonal matrix and R an upper triangular matrix, wherein said step of generating the reference child node comprises projecting said vector representing the received signal on a layer of said upper triangular matrix.

### Claim 3 (depends on 2)

The method of claim 2, wherein said reference child node is further generated from the values of the tree nodes comprised in the path from the root node to the current node.

### Claim 4 (depends on 3)

The method as claimed in claim 3, wherein said step of generating said reference child node comprises determining the reference child node from the nearest integer of a quantity
1
R
ii
⁢
(
y
~
i
-
∑
j
=
i
+
1
n
⁢
R
ij
⁢
s
j
)
,
where i designates the level of the reference child node in the tree, Rii represents the component (i,i) of the upper triangular matrix R, Rij represents the component (i,j) of the upper triangular matrix R where j varies from i+1 to n, and {tilde over (y)}i represents the ith component of the received signal {tilde over (y)}.

### Claim 5 (depends on 4)

The method as claimed in claim 4, wherein said step of generating the reference child node comprises determining a metric (fi(si)) associated with the reference child node (si) from the weight metrics ((w(sj)) of the nodes in the tree comprised in the path from the root node to the current node.

### Claim 6 (depends on 5)

The method as claimed in claim 5, wherein said metric associated with the reference child node (si) is represented by the cumulated weight determined from the sum of the weight metrics ((sj)) of the nodes in the tree comprised in the path from the root node to the current node, the weight metric ((sj)) of a node at a given level j of the tree being determined as the Euclidean distance between the jth component of the vector {tilde over (y)} representing the received signal and a vector ((sn . . . sJ)) comprising the nodes of the tree from the root node to the node at level j.

### Claim 7 (depends on 5)

The method as claimed in claim 5, wherein said metric associated with the reference child node (si) is represented by the cumulated weight determined from the sum of the weight metrics ((sj)) of the nodes in the tree comprised in the path from the root node to the current node, the weight metric ((sj)) of a node at a level j of the tree being determined as the difference between:
the Euclidean distance between the jth component of the vector {tilde over (y)} representing the received signal and a vector (sn . . . sj) comprising the values of the nodes of the tree from the root node to the node at level j, and
the product of a predefined bias parameter b by the level j, wherein the predefined bias parameter is a real and positive value.

### Claim 8 (depends on 7)

The method as claimed in claim 7, wherein said step of storing at most three child nodes in the stack further comprises storing auxiliary parameters in association with each node in the stack, said auxiliary parameters comprising the node path, and wherein said estimation of the data signal is determined from said node paths stored in the stack.

### Claim 9 (depends on 8)

The method as claimed in claim 8, wherein said step of selecting the top node further comprises determining if the node selected in the stack is a leaf node and wherein the method comprises:
performing the next iteration if the selected node is not a leaf node, and
terminating the iterations if the selected node is a leaf node.

### Claim 10 (depends on 1)

The method as claimed in claim 1, wherein the method comprises, for each iteration, storing each path from a root node to a leaf node in an auxiliary stack,
said estimation of the data signal being further determined from the node information stored in said auxiliary stack.

### Claim 11 (depends on 10)

The method as claimed in claim 10, wherein each of said steps of generating a child node among the reference child node, the first child node and the second child node comprises determining if the generated nearest integer to the value of the child node is comprised between said minimum threshold and said maximum threshold, the method further comprising for at least one of the three generated child nodes:
if the generated nearest integer to the value of the child node is comprised between said minimum threshold and said maximum threshold, setting the child node to the nearest integer value within the constellation range.

### Claim 12 (depends on 11)

The method as claimed in claim 11, wherein the method further comprises:
if the generated nearest integer to the value of the child node is lower than the predefined minimum threshold, setting the child node value as equal to said minimum threshold;
if the generated nearest integer to the value of child node is higher than said maximum threshold, setting the child node value as equal to the maximum threshold.

### Claim 13 (depends on 12)

The method of claim 12, wherein said communication system is a multi-antenna system and said transmission channel is associated with a channel matrix H of a given dimension, said received data signal yc being equal to Hcsc+wc, with Hc, sc and wc corresponding respectively to the complex value of the channel matrix H, of the vector s representing the transmitted data signal and of a noise vector w, and wherein the received data signal is previously transformed into a real-valued representation, said representation being defined by the following formula:
y
=
[
⁢
(
H
c
)
-
⁢
(
H
c
)
⁢
(
H
c
)
⁢
(
H
c
)
]
⁡
[
⁢
(
s
c
)
⁢
(
s
c
)
]
+
[
⁢
(
w
c
)
⁢
(
w
c
)
]
=
Hs
+
w
where (.) and (.) denote respectively the real and imaginary parts of the complex-valued vector specified as parameter.

### Claim 14

A computer program product for decoding a received data signal, the computer program product comprising:
a non-transitory computer readable storage medium; and
instructions stored on the non-transitory computer readable storage medium that, when executed by a processor, cause the processor to:
iteratively construct a decoding tree, each node of said decoding tree corresponding to a component of a symbol of said data signal, and being associated with a metric, wherein said step of iteratively constructing the decoding tree implements at least one iteration of the following steps, for a current node of the tree stored in the top of a stack:
generating a reference child node (si) of said current node from said vector representing the received data signal,
from the reference child node (si), generating a first neighbor child node by subtracting a positive integer parameter (p) from the value of the reference node (si), and a second neighbor child node by adding said positive integer parameter (p) to the value of the reference child node (si);
storing in said stack at most three child nodes among the reference child node and said first and second neighbor child nodes, each child node being stored in the stack in association with node information comprising a predetermined metric, the nodes in the stack being ordered by increasing values of metrics;
removing the current node from said stack;
selecting the top node of said stack as the new current node;
wherein the value of each node in the tree corresponds to the component of a symbol belonging to a given constellation having a predefined range between a minimum threshold and a maximum threshold, each step of generating a child node comprising setting the value of the child node based on said maximum and minimum thresholds,
wherein said instructions further cause the processor to determine an estimation of said data signal from the node information stored in said stack.

### Claim 15

A device for decoding a received data signal, wherein the device comprises:
at least one processor; and
a memory coupled to the at least one processor and including instructions that, when executed by the at least one processor, cause the device to iteratively construct a decoding tree, each node of said decoding tree corresponding to a component of a symbol of said data signal, and being associated with a metric, wherein said step of iteratively constructing the decoding tree implements at least one iteration of the following steps, for a current node of the tree stored in the top of a stack:
generating a reference child node (si) of said current node from said vector representing the received data signal,
from the reference child node (si), generating a first neighbor child node by subtracting a positive integer parameter (p) from the value of the reference node (si), and a second neighbor child node by adding said positive integer parameter (p) to the value of the reference child node (si);
storing in said stack at most three child nodes among the reference child node and said first and second neighbor child nodes, each child node being stored in the stack in association with node information comprising a predetermined metric, the nodes in the stack being ordered by increasing values of metrics;
removing the current node from said stack;
selecting the top node of said stack as the new current node;
wherein the value of each node in the tree corresponds to the component of a symbol belonging to a given constellation having a predefined range between a minimum threshold and a maximum threshold, each step of generating a child node comprising setting the value of the child node based on said maximum and minimum thresholds,
wherein said instructions, when executed by at least one processor, further cause the device to determine an estimation of said data signal from the node information stored in said stack.