ENCODER, DECODER, ENCODING AND DECODING SYSTEM, ENCODING AND DECODING METHOD, ENCODING PROGRAM, DECODING PROGRAM, ENCODING AND DECODING PROGRAM, AND RECORDING MEDIUM

摘要

PROBLEM TO BE SOLVED: To extremely shorten a search time for the nearest vector by extremely reducing the size of a database. SOLUTION: This encoder 4 includes: a typical vector searching device 4-1 which takes one k-dimensional vector s(i) having an index i present in a syndrome database 4-2 and outputs an n-dimensional typical vector 4-7(y) satisfying Ay=s and an index 4-8(i) to a given linear matrix 4-3(A); and a multiplier 4-5 which finds a vector By by multiplying a linear matrix 4-5 by the typical vector 4-7(y). The encoder 4 outputs, as a codeword 4-9, a set of the index 4-8(i) which has been found by the typical vector searching device 4-1 and has been encoded by [log2m] bits and the vector By encoded by [1 times log2¾W¾] bit. COPYRIGHT: (C)2008,JPO&INPIT