Title:
ADAPTIVE LINEAR PROGRAMMING DECODING METHOD
Document Type and Number:
WIPO Patent Application WO/2019/230371
Kind Code:
A1
Abstract:
The purpose of the present invention is to provide an ALP decoding method in which decoding by ALP of a hamming code is achieved, and as a result, implementation load of the decoding method can be reduced and computation time can be shortened. An ALP decoding method, provided with: a factor graph generation step for generating a factor graph of a hamming code defined by a prescribed check matrix; a constraint condition derivation step for deriving a constraint condition of a number node on the basis of a condition expression that a variable node ought to satisfy; an isolated variable node detection step for detecting an isolated variable node connected to a check node, from among variable nodes connected to a plurality of check nodes from the generated factor graph; a restriction addition step for adding a restriction in that the isolated variable node is an integer value; and a decoding result calculation step for calculating, on the basis of the constraint condition and information relating to the isolated variable node to which the restriction has been added, a solution by MILP and deeming the solution to be the result of decoding the hamming code.
Inventors:
USHIZAKA HIRONORI (JP)
Application Number:
PCT/JP2019/019128
Publication Date:
December 05, 2019
Filing Date:
May 14, 2019
Export Citation:
Assignee:
NIPPON TELEGRAPH & TELEPHONE (JP)
International Classes:
H03M13/19
Other References:
TAGHAVI H. MOHAMMAD ET AL.: "Efficient Implementation of Linear Programming Decoding", IEEE TRANSACTIONS ON INFORMATION THEORY, vol. 57, no. 9, 30 August 2011 (2011-08-30), pages 5960 - 5982, XP011382319, DOI: 10.1109/TIT.2011.2161920
ZHANG XIAOJIE ET AL.: "Adaptive cut generation for improved linear programming decoding of binary linear codes", 2011 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY PROCEEDINGS, vol. 58, no. 10, 3 October 2011 (2011-10-03), pages 1638 - 1642, XP080505324
FALSAFAIN HOSSEIN ET AL.: "Stopping Set Elimination by Parity-Check Matrix Extension via Integer Linear Programming", IEEE TRANSACTIONS ON COMMUNICATIONS, vol. 63, no. 5, 31 March 2015 (2015-03-31), pages 1533 - 1540, XP011581511, DOI: 10.1109/TCOMM.2015.2418263
FUJIE TETSUYA: "Introduction to formulation by integer programming", OPERATIONS RESEARCH SOCIETY OF JAPAN, vol. 57, no. 4, 2012, pages 190 - 197
ZHANG XIAOJIE ET AL.: "Adaptive cut generation for improved linear programming decoding of binary linear codes", 2011 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY PROCEEDINGS, vol. 58, no. 10, 3 October 2011 (2011-10-03), pages 1638 - 1642, XP080505324
FALSAFAIN HOSSEIN ET AL.: "Stopping Set Elimination by Parity-Check Matrix Extension via Integer Linear Programming", IEEE TRANSACTIONS ON COMMUNICATIONS, vol. 63, no. 5, 31 March 2015 (2015-03-31), pages 1533 - 1540, XP011581511, DOI: 10.1109/TCOMM.2015.2418263
FUJIE TETSUYA: "Introduction to formulation by integer programming", OPERATIONS RESEARCH SOCIETY OF JAPAN, vol. 57, no. 4, 2012, pages 190 - 197
Attorney, Agent or Firm:
YAMAKAWA, Shigeki et al. (JP)
Download PDF: