JP2014110533A - Encoding device, method and program, and recording medium - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide technology for encoding information on the basis of technology for a series of random numbers conforming to second probability distribution.SOLUTION: Processing by a probability distribution generation unit which generates third probability distribution which is a distribution of third probabilities about all of instances that can be taken on, assuming a third probability, which is a probability about instances, to be a probability corresponding to a product of a first probability with which an instance of a series of already generated random numbers occurs when it is made a condition, and a second probability with which a series of remaining random numbers generated next time and on satisfies a prescribed condition when the series of already generated random numbers and random numbers generated this time are made conditions, and processing by a random number generation unit which generates one instance as a random number according to the of distribution third probabilities are executed repeatedly. The prescribed condition is a condition representing the relationship between message and prescribed shared information and a series of a plurality of values by using a prescribed function.

Description

  The present invention relates to a technique for encoding information.

  The probability of an actual value that is a sequence of a plurality of values is a probability corresponding to the probability that the actual value appears in a predetermined first probability distribution, and the actual value that is a sequence of all the multiple values that satisfy a predetermined condition A technique for generating a sequence of random numbers according to the second probability distribution, which is the probability distribution of the above, and a technique for encoding information based on this technique have not been proposed so far.

  An object of the present invention is to provide an encoding apparatus, method, program, and recording medium for encoding information based on a technique for generating a sequence of random numbers according to the second probability distribution.

  An encoding apparatus according to an aspect of the present invention sets a probability for an actual value that is a sequence of a plurality of values as a probability corresponding to a probability that the actual value appears in a predetermined first probability distribution, and satisfies all the predetermined conditions The probability distribution for the realized value that is a series of a plurality of values is defined as the second probability distribution, and the third probability that is the probability for the realized value is the condition when the already generated random number sequence is used as a condition. Product of the first probability of occurrence and the second probability that the sequence of random numbers that have already been generated and the random number that is generated this time satisfy the predetermined condition A probability distribution generation unit that generates a third probability distribution that is a distribution of the third probability for all possible real values, and a random number generator that generates one real value as a random number according to the third probability distribution Part and probability distribution students And a control unit that generates a sequence of random numbers according to the second probability distribution by repeating the processing of the unit and the random number generation unit, and the predetermined condition includes a message and predetermined shared information, and a sequence of a plurality of values This is a condition expressing the relationship using a predetermined function.

  Information can be encoded based on a technique for generating a sequence of random numbers according to the second probability distribution.

The block diagram for demonstrating the example of a random number series production | generation apparatus. The block diagram for demonstrating the other example of a random number series production | generation apparatus. The flowchart for demonstrating the example of the random number series production | generation method. The block diagram for demonstrating the example of the encoding apparatus and decoding apparatus of 1st embodiment. The block diagram for demonstrating the example of the encoding apparatus and decoding apparatus of 1st embodiment. The block diagram for demonstrating the example of the encoding apparatus and decoding apparatus of 2nd embodiment. The block diagram for demonstrating the example of the encoding apparatus and decoding apparatus of 2nd embodiment. The block diagram for demonstrating the example of the encoding apparatus and decoding apparatus of 3rd embodiment. The block diagram for demonstrating the example of the encoding apparatus and decoding apparatus of 4th embodiment. The flowchart for demonstrating the example of the encoding method. The flowchart for demonstrating the example of a decoding method.

[Description of notation]
First, the notation is explained. When X is a random variable, the set of possible values of X is denoted as [X]. The size of the set S, that is, the number of elements included in the set S is denoted as | S |. The difference set is denoted as S \ S ′, which represents a set that is included in the set S and is composed of all the elements that are not included in the set S ′.

X ⁿ ≡ (X ₁ , X ₂ ,..., X _n ) is an n-dimensional random variable, and its realization value is denoted as x ⁿ ≡ (x ₁ , x ₂ ,..., X _n ).
[X ⁿ ] ≡ [X ₁ ] × [X ₂ ] ×… × [X _n ]. The probability distribution corresponding to the random variable X is denoted as p _X. It should be noted, it is sometimes referred to as p_ the p _{X (X).}

Φ generally represents a function, and Φ (x ⁿ ) represents the value of the function Φ in the vector x ⁿ . If q is a prime number and the function Φ: GF (q) ⁿ → GF (q) ^m is a linear mapping of the vector space over the finite field GF (q) of q,

It is expressed as a matrix. Where x ⁿ is a column vector

It becomes. In this case, Φ (x ⁿ ) is denoted as Φx ⁿ .

  If it is not explicitly stated that the set of possible values of a variable is finite, continuous values can be taken. If the variable for which the sum Σ is taken is a continuous value, Σ is an integral ∫.

[A simple random number generation method that satisfies the constraints]
Φ (x ⁿ ) ∈V ₁ × V ₂ ×… × V _l for a set of functions Φ≡ {φ _s : [X ⁿ ] → V _s } _{s = 1} ^l

It is defined as Given the distribution p _X ^{n of} v ^l ≡ (v ₁ , v ₂ , ..., v _l ) and the random variable X ⁿ ≡ (X ₁ , X ₂ , ..., X _n ), Consider μ (x ⁿ ).

When the predetermined condition is Φ (x ⁿ ) = v ^l and the predetermined first probability distribution is p _X ⁿ , the probability μ (x for the real value x ⁿ ≡ (x ₁ , x ₂ , ..., x _n ) ⁿ ) is a probability corresponding to the probability that the actual value x ⁿ appears in the predetermined first probability distribution p _X ⁿ .

Here, any one real value x ⁿ according to the distribution (second probability distribution) of the probability μ (x ⁿ ) for all real values satisfying the predetermined condition Φ (x ⁿ ) = v ^l is used as a sequence of random numbers. Two simple methods to generate are described.

<Method 1>
First, a set Ω that enumerates x ⁿ satisfying Φ (x ⁿ ) = v ^l is obtained. Then, for each x ⁿ ∈Ω, the relational expression

The probability distribution μ is obtained by calculating the right side of (a2) using. Finally, x ⁿ ∈Ω is selected according to the probability distribution μ.

In <Method 1>, the input is p _X ⁿ , the function set Φ and the vector v ^l , and the output is a random number x ⁿ .

<Method 2>
Select x ⁿ ∈ [X ⁿ ] according to the probability distribution p _X ⁿ . Then, x ⁿ to see if it meets the conditions ^{Φ (x n) = v l} . This is repeated until x ⁿ satisfying Φ (x ⁿ ) = v ^l is selected. Finally, x ⁿ satisfying this condition is output as a sequence of random numbers, and the process ends.

In <Method 2>, the input is p _X ⁿ , the function set Φ and the vector v ^l , and the output is a random number x ⁿ .

In <Method 1>, it is necessary to obtain a set Ω that enumerates x ⁿ satisfying Φ (x ⁿ ) = v ^l , but in general, | Ω | increases exponentially as n increases. It can be difficult to find. Since this fact makes it difficult to calculate (a3), it may be difficult to obtain the probability distribution μ. Moreover, even if the probability distribution μ is obtained, it may be difficult to select x ⁿ ∈Ω according to μ. Furthermore, when p _X ⁿ is fixed in advance, Ω and μ can be calculated in advance and recorded in the storage unit, but in this case, the storage amount may increase exponentially with n. is there.

In <Method 2>, random numbers are repeatedly generated until x ⁿ satisfying Φ (x ⁿ ) = v ^l is selected. Generally, the probability of selecting x ⁿ satisfying Φ (x ⁿ ) = v ^l is an exponent together with n. Since it approaches zero, the number of iterations may increase exponentially.

[First Embodiment of Random Number Sequence Generation Apparatus and Method]
In the following, a set of functions Φ≡ {φ _s : [X ⁿ ] → V _s } _{s = 1} ^l and v ^l ≡ (v ₁ , v ₂ ,…, v _l ) are given, and Φ (x ⁿ ) ∈V A random number sequence generation device that generates a sequence x ⁿ of random numbers according to the probability distribution μ of (a2) when ₁ × V ₂ ×... × V _l is defined by (a1) will be described.

T (s) ⊂ {1,2, ..., n} is used to calculate the function φ _s (x ⁿ ) and the set of indices of variables x ⁿ ≡ (x ₁ , x ₂ , ..., x _n ) To do. Let _{xT (s) be} a | T (s) | -dimensional vector obtained by extracting a portion corresponding to the index set T (s) from ^xn . In the following, focusing on only variables used in calculating the function φ _s (x ⁿ ), φ _s (x ⁿ ) is ^denoted as φ _s (x _{T (s)} ). For example, if the variables used when calculating the function φ _s (x ⁿ ) are x ₁ and x ₂ , T (s) = {1,2}, φ _s (x _{T (s)} ) ≡φ _s (x ₁ , x ₂ ) = φ _s (x ⁿ ) is satisfied.

Χ (x _{T (s)} , v _s ) determined from Φ≡ {φ _s : [X ⁿ ] → V _s } _{s = 1} ^l is defined as follows.

The probability distribution p _X ⁿ is decomposed as follows.

  Here, when t = 1 on the right side of the above equation

And For example, if p _X ⁿ is memoryless,

When p _X ⁿ has δ-order Markov property

It becomes.
As shown in FIG. 1, the random number sequence generation device 1 includes, for example, a control unit 11, a probability distribution generation unit 12, a random number generation unit 13, a storage unit 14, and a random number estimation unit 15.

In order to generate random numbers according to the probability distribution μ defined in (a2), the random number sequence generation device executes the following processing. In the following, Σ represents the sum of all possible values of the variable written below. For example, Σ _xt is the sum over all x _t ∈ [X _t ].

  The control unit 11 sets k = 1 (step A1, FIG. 3).

The probability distribution generation unit 12 obtains a function f _k (x _k ) defined by the following equation (step A2). The function f _k (x _k ) can be obtained, for example, by executing a sum-product algorithm. The sum-product algorithm will be described later.

In the right side of the above equation, x ₁ ,..., X _k−1 recorded so far are substituted.

Further, if a record in which χ (x _{T (s)} , v _s ) is a constant is recorded, future calculations can be omitted. For example, if T (s) is {1, ..., k}, the value of χ (x _{T (s)} , v _s ) is 0 or 1 regardless of the values of x _{k + 1} , ..., x _n And become a constant. In this case, a constant χ (x _{T (s)} , v _s ) is recorded in the storage unit 14 for use in the next and subsequent iterations.

x ₁ , ..., x _k-1 is a sequence of already generated random numbers, a random number generated this time is x _k, and a sequence of remaining random numbers generated after the next time is x _{k + 1} , ..., x _n Then, it appears in the molecule on the right side of (a5)

Can be said to be the first probability that the realization value x _t appears when the sequence of generated random numbers x ₁ ,..., X _t−1 is used as a condition.

  It also appears in the molecule on the right side of (a5)

Is a sequence of random numbers x ₁ ,..., X _k−1 that have already been generated and a random number x _k that is generated this time, and the remaining random number sequences x _{k + 1} ,. It can be said that x _n is a second probability that satisfies a predetermined condition (in this case, Φ (x ⁿ ) = v ^l ).

Since the denominator of (a5) is a normalized term, for example, f _k (x _k ) represented by (a5) is a probability distribution whose real value is a value corresponding to the product of the first probability and the second probability. It can be said.

The random number generation unit 13 generates a random number x _k according to the probability distribution f _k (x _k ) and records it in the storage unit 14 (step A3).

  The controller 11 determines whether k = n (step A4).

If k = n, the control unit 11 outputs x ⁿ ≡ (x ₁ , x ₂ ,..., x _n ) obtained by concatenating the values of the variables recorded so far, and ends (step A5).

If k <n, the control unit 11 determines the remaining variable values (x _{k + 1} ,..., x) satisfying Φ (x ⁿ ) = v ^l from (x ₁ ,..., x _k ) recorded so far. It is confirmed whether or not x _n ) is uniquely determined (step A6).

If If the only determined, the random number estimating unit 15 _{(x k + 1, ...,} x n) x n ≡ (x 1, x 2, ..., x n) seeking to terminate with a (step A7 ). An example of a criterion for confirming whether or not it is determined and an example of how to obtain (x _{k + 1} ,..., X _n ) in this case will be described in the second embodiment of the random number sequence generation device and method.

  If not uniquely determined, the controller 11 increases the value of k by 1 and returns to step A2 (step A8).

  In this manner, the control unit 11 repeats the processing of the probability distribution generation unit 12 and the random number generation unit 13 to generate a random number sequence according to the probability distribution μ.

Note that the processing of step A6 and step A7 may not be performed. For example, if it takes time to confirm whether (x _{k + 1} , ..., x _n ) is uniquely determined or if this confirmation cannot be performed, it is also determined (x _{k + 1} , ..., x _{If the} process for obtaining _n ) takes time or cannot be performed, the confirmation process may be omitted, and if k <n, the value of k may be increased by 1 and the process may return to step A2. In this case, the random number sequence generation device 1 may not include the random number estimation unit 15 as illustrated in FIG.

The input of the random number sequence generator 1 is a set of probability distributions {p_ (X _t | X ₁ ^t-1 )} _{t = 1} ⁿ and a set of functions {χ (x _{T (s)} , v _s )} _{s = 1} ^l And the output of the random number sequence generation device 1 is ^xn . As described above, the storage unit 14 may record data in which χ (x _{T (s)} , v _s ) becomes a constant in addition to the input.

When calculating (a5) in step A2, the variable of interest (x _{k in the} above) can be freely selected from the variables (x _k , x _{k + 1} ,..., X _n ). Therefore, in step A2, a marginalization function that is convenient for later calculations can be used from the result of obtaining the marginalization function for all variables (x _k , x _{k + 1} ,..., X _n ). . This means that the order of marginalizing the variables (x ₁ ,..., X _n ) can be adaptively changed in step A2. Here, it should be noted that re-calculation of p_ (X _n | X ₁ ^t−1 ) appearing on the right side of (a5) may be required in accordance with the change of the order of the variables of interest. However, when p _X ⁿ is memoryless, that is, satisfies (a4), the variable to be noted among the variables (x _k , x _{k + 1} ,..., X _n ) when calculating (a5) in step A2. Even if (x _{k in the} above) is changed, it is not necessary to recalculate p_ (X _t | X ₁ ^t−1 ) = p _{Xt according to} the change of the order of the variables of interest.

Note that a random number generation algorithm that satisfies the constraint conditions may be applied after the conditional expression is transformed into a conditional expression that is equivalent to the conditional expression Φx ⁿ = v ^l and that improves the calculation accuracy of the sum-product algorithm.
In order to increase the approximation accuracy of sum-product, for example, the condition is set so that the size of the set T (s) becomes small and the factor graph corresponding to the conditional expression Φx ⁿ = v ^l does not have a short loop. It is conceivable to change the formula.

In order to generate a desired random number in step A2, x _k may be obtained from the uniform random number sequence using the interval algorithm described in Reference Document 1. In Reference Document 1, it is assumed that the generated random number sequence has independent and same distribution. However, since this assumption does not hold here, the following improvements are applied. Now, suppose that there is a sufficiently long uniform ω-element random number sequence r ₁ , r ₂ ,. This random number sequence r ₁ , r ₂ ,... Is generated by, for example, the uniform random number generation unit 16 indicated by a broken line in FIG. Below
[ζ, η) ≡ {θ: ζ ≦ θ <η}
And

  [Reference 1] [11] TS Han and M. Hoshi, “Interval algorithm for random number generation,” IEEE Trans. Inform. Theory, vol. IT-44, no. 2, pp. 599-611, Mar. 1997 .

In step A1, the initial value of the section is set to [ζ ₁ , η ₁ ) ≡ [0,1).

In step A3, the section [ζ _k , η _k ) is divided into partial sections of length {f _k (x)} _{x∈ [Xk]} , and the section corresponding to the length f _k (x) is labeled x∈ [ Add X _k ]. Then, the corresponding label and ω advance decimal 0.r ₁ r ₂ ... section, including the x _k. At the end of step A2, a section corresponding to the previously obtained x _k , that is, a section including the ω-adic decimal 0.r ₁ r ₂ ... Is set as [ζ _{k + 1} , η _{k + 1} ).

With this improvement, the width of the interval corresponding to x ⁿ = (x ₁ , ..., x _n ) becomes μ (x ⁿ ), so the interval corresponding to (x ₁ , ..., x _n ) The probability that the obtained ω-adic decimal 0.r ₁ r ₂ ... Is included is μ (x ⁿ ). Here, when the algorithm stops at k = k ′, random numbers are generated only until (x ₁ ,..., X _{k ′} ), but the division of the section at the time point of k = k ′ corresponds to (a11) described later. Therefore, a random number sequence (x ₁ ,..., X _n ) according to a desired probability distribution is obtained.

Assuming that the sum-product algorithm is applied at step A2 and executed at O (n), and assuming that the calculation time at step A6 and step A7 is O (n ² ), this algorithm is End with the computation time of O (n ² ). For this reason, this algorithm can generate a random number sequence in a shorter calculation time than the above-mentioned [simple random number sequence generation method that satisfies the constraint conditions].

  In the following, it is proved that this algorithm outputs the expected result. The expression that appears in the numerator on the right side of (a5)

Then,

Is true.

Let x ⁿ = (x ₁ , x ₂ ,..., x _n ) be the finally output random number sequence. If it ends with k = n in step A4 of the algorithm,

It becomes. On the other hand, when k = k ′ <n ends in step A6 and step A7 of the algorithm, the remaining variables satisfying Φ (x ⁿ ) = v ^l from (x ₁ , x ₂ ,..., X _{k ′} ) Since the value of (x _{k '+ 1} , ..., x _n ) is only determined,

It becomes. Since (a8) includes (a7) as the case of k ′ = n, the case where it ends with k = k ′ will be considered below.

  When k ≧ 2 from (a6)

Holds. And when k = 1

Holds. The probability of finally outputting x ⁿ from (a8), (a9), and (a10) is

It becomes. Therefore, this algorithm outputs a random number sequence x ⁿ according to the probability distribution (a2).

<About the sum-product algorithm>
In general, the sum-product algorithm means that when a function e _s (x _{T (s)} ) determined by a variable vector x _{T (s)} consisting of a part of a variable vector x ⁿ is given by each s∈S, Function

It is a procedure to ask for. Here, T (s) ⊂N for each s∈S, where N≡ {1, 2,..., N}. Σ _{xn \ {xt}} is the sum when all the values of x ⁿ other than the variable x _t appearing in the vector x ⁿ are moved. Also, it appeared in the numerator on the right side instead of g (x _t ) defined in (a12)

In some cases, a sum-product algorithm is described as a procedure for obtaining. However, hereinafter, a procedure for obtaining g (x _t ) defined in (a12) is referred to as a sum-product algorithm.

The sum-product algorithm is described below. Functions π _{xt → es} (x _t ) and σ _{es → xt} (x _t ) called messages are defined as follows.

Here, Σ _{x_ (T (s) \ {t})} is the sum when all {x _{t '} } _{t'∈T (s) \ {t}} are moved, and Σ _{x_ (T (s) )} Represents the total sum when all {x _t } _{t∈T (s)} are moved. And when T (s) = {t}

When there is no s'∈S \ {s} that satisfies x _t ∈T (s')

It is determined.
Hereinafter, specific processing of the sum-product algorithm will be described.
Step 1 For t∈N, s∈S satisfying T (s) = {t}

And initialize.
_{Step 2 x t ∈T (s'} ) as s'∈S\ {s} does not exist that meets the T∈N, against s∈S

And initialize.
Step 3 For t∈N and s∈S satisfying t∈T (s), if π _{xt → es} (x _t ) is not initialized in Step 2, set an appropriate initial value. For example, if the set of possible values of x _t is [X _t ],

And
Step 4 Find σ _{es → xt} (x _t ) by (a13) for all t∈N, s∈S that satisfy t∈T (s). Here, for the combination of s and t initialized in Step 1, the calculation of σ _{es → xt} (x _t ) is omitted.
Step 5 Find π _{xt → es} (x _t ) by (a14) for all t∈N, s∈S that satisfy t∈T (s). Here, for the combination of s and t initialized in Step 2, the calculation of π _{xt → es} (x _t ) is omitted.
Step 6 Step 4 and Step 5 are repeated a predetermined number of times, and then the following function is obtained and finished.

  When using the sum-product algorithm for the random number generation algorithm that satisfies the constraints, in (a5)

Is applied as {e _s } s∈S. The right side of (a15) obtained after execution of the sum-product algorithm is an approximate expression of f _k (x _k ).

[Second Embodiment of Random Number Sequence Generation Apparatus and Method]
The second embodiment of the random number sequence generation device and method is a random number sequence generation device and method when the function has linearity. Below, it demonstrates centering on a different part from 1st embodiment of a random number sequence generation apparatus and method, and it abbreviate | omits duplication description about the part similar to 1st embodiment of a random number sequence generation apparatus and method.

In the following, [X ₁ ] = [X ₂ ] =… = [X _n ] = [V ₁ ] = [V ₂ ] =… = [V _l ] = GF (q), where l ≦ n, Full rank l × n matrix

think of. Function φ _s : [X ⁿ ] → V _s

It is defined as The right side of the above equation is the n-dimensional vector (φ _{s, 1} , φ _{s, 2} ,..., Φ _{s, n} ) and x ⁿ ≡ (x ₁ , x ₂ , ..., x _n of the matrix Φ ) ∈ [X _n ] inner product.

Φ≡ {φ _s } _{s = 1} ^l and vector defined as above

The specific processing of the random number sequence generation device 1 for generating a distribution determined by the probability distribution (a2) will be described.

Here, Φ and v ^l may use the given matrix and vector as they are, but the following matrix connecting Φ and v ^l

Result of applying row basic transformation to

Left l × n matrix Φ'and right l × 1 matrix (l-dimensional vector) v ^'l, may be substituted as Φ and v ^l, respectively. For example, by using Φ ′ and v ′ ^l such that the factor graph determined from Φ ′, x ^n, and v ′ ^l does not have a short loop due to many components that are 0 in the matrix Φ ′, the sum-product algorithm is used. Since the approximation accuracy may be improved, the accuracy of the probability distribution of the random numbers output by the random number sequence generation device of the present invention can be further improved.

Hereinafter, even if it is assumed that Φ is a full rank matrix and the l × l matrix Ψ ₂ on the right side of the matrix Φ is a regular matrix, the generality is not lost. In practice, a matrix obtained by removing redundant Φ rows and v ^l components from an arbitrary matrix Φ and vector v ^l is obtained, and the row vector and variable (x ₁ , x ₂ , ..., A desired matrix can be obtained by appropriately rearranging the order of x _n ).

Assuming that the l × (nl) matrix on the left side of the matrix Φ is Ψ ₁ , from the above assumption, if x ^nl ≡ (x ₁ , ..., x _nl ) is determined
(x _{n-l + 1} ,…, x _n ) ≡Ψ ₂ ^-1 (v ^l -Ψ ₁ x ^nl )
The remaining variables (x _{n−l + 1} ,..., X _n ) satisfying Φx ⁿ = v ^l can be obtained. Here, Ψ ₂ ⁻¹ represents an inverse matrix of Ψ ₂ and can be obtained before the algorithm is executed.

T (s, k) ⊂ {k, ..., n} is a set of indices s satisfying φ _{s, t} ≠ 0 among vectors (φ _{s, k} , ..., φ _{s, n} ) appearing in the matrix Φ To do. That is, T (s, k) is defined as follows.
T (s, k) ≡ {t∈ {k,…, n}: φ _{s, t} ≠ 0}

Here, χ (x _{T (s, k)} , v _s (k)) is defined as follows.

  With the above settings, the specific processing of the random number sequence generation device 1 can be changed as follows.

The control unit 11 sets k = 1. Let _s (k) = v _s for each s∈ {1, ..., l}.

The probability distribution generation unit 12 obtains a function f _k (x _k ) defined by the following equation (step A2). The function f _k (x _k ) can be obtained, for example, by executing a sum-product algorithm.

Random number generator 13 generates a x _k with probability distribution f _k (x _k), and records in the storage unit (step A3).

  The controller 11 determines whether k = n (step A4).

If k = n, the control unit 11 outputs x ⁿ ≡ (x ₁ , x ₂ ,..., x _n ) obtained by concatenating the values of the variables recorded so far, and ends (step A5).

If k <n, the control unit 11 determines the remaining variable values (x _{k + 1} ,..., x _n ) satisfying Φx ⁿ = v ^l from (x ₁ ,..., x _k ) recorded so far. To see if it is the only one. In this example, the control unit 11 determines whether k = l (step A6).

If k = l, the random number estimator 15 calculates and records the remaining variable values (x _{l + 1} ,..., x _n ) ≡Ψ ₂ ⁻¹ v ^l (k + 1), and so far The recorded x ⁿ ≡ (x ₁ , x ₂ ,..., X _n ) is output and the process ends (step A7).

If k <l, the control unit 11 increases the value of k by 1, and returns to step A2 (step A8). When returning to step A2, v _l (k + 1) ≡ (v ₁ (k + 1),..., V _l (k + 1)) is expressed as s∈ {1,.
v _s (k + 1) ≡v _s (k) -φ _{s, k} x _k
And

In the above specific processing, the processing of step A4 and step A5 may be omitted, and the processing may proceed immediately from step A3 to step A6. Alternatively, if it takes time to calculate Ψ ₂ ⁻¹ v ^l (k + 1) in step A7, the processing of step A6 and step A7 may be omitted, and the process may proceed immediately from step A4 to step A8.

The input of the random number sequence generation device 1 of the second embodiment is a set of probability distributions {p_ (X _t | X ₁ ^t−1 )} _{t = 1} ⁿ and a matrix Φ, and the output is x ⁿ . In addition to the input q and information q necessary for calculating GF (q), Ψ ₂ ⁻¹ can be obtained from Φ and recorded in the storage unit 14. (x _{T (s, k)} , v _s (k)) is updated with Φ using k.

[Third embodiment of random number sequence generation apparatus and method]
The third embodiment of the random number sequence generation device and method is a random number sequence generation device and method when p _X ⁿ is a conditional probability distribution. Below, it demonstrates centering on a different part from 1st embodiment of a random number sequence generation apparatus and method, and it abbreviate | omits duplication description about the part similar to 1st embodiment of a random number sequence generation apparatus and method.

Given a conditional probability distribution p_ (X ⁿ | U ⁿ ), it satisfies the constraints,

When generating random numbers according to

And the specific process of the random number sequence generation device is executed. That is, for example, (a5) is expressed by the following equation.

The input of the random number sequence generation device 1 of the third embodiment is a set of probability distributions {p_ (X _t | X ₁ ^t−1 U ⁿ )} _{t = 1} ⁿ , a set of functions Φ, v ^l , u ⁿ , The output is ^xn .

  In addition to input, the storage unit 14

The information necessary for calculating is stored and used for calculating the probability distribution.

Similarly to the above, p _X ⁿ may be a conditional probability distribution also in the second embodiment of the random number sequence generation device and method.

[Fourth Embodiment of Random Number Sequence Generation Apparatus and Method]
The fourth embodiment of the random number sequence generation device and method is a random number sequence generation device and method when a constraint condition is described using a plurality of functions having the same domain. Below, it demonstrates centering on a different part from 1st embodiment of a random number sequence generation apparatus and method, and it abbreviate | omits duplication description about the part similar to 1st embodiment of a random number sequence generation apparatus and method.

Let c∈C. C is a predetermined constant of 2 or more. In the random number generation method that satisfies the constraints, a set of functions with the same domain Φ _c ≡ {φ _{c, s} : [X ⁿ ] → V _{c, s} } _{s = 1} ^lc
as well as
v _c ^lc ≡ (v _{c, 1} , v _{c, 2} ,…, v _{c, l} ) ∈V _{c, 1} × V _{c, 2} ×… × V _{c, lc}
And the distribution p _X ⁿ is given,

To generate random numbers according to

In the meantime, the specific processing of the first embodiment of the random number sequence generation apparatus and method may be executed.
That is, for example, (a5) is expressed by the following equation.

Where T (c, s) ⊂ {1,2, ..., n} is the variable x ⁿ = (x ₁ , x ₂ ) used in calculating φ _{c, s} (x ⁿ ) = v _{c, s} ,…, X _n )

It is.
Of course, when all the functions Φ _c are linear mappings (matrixes), the specific processing of the second embodiment of the random number sequence generation apparatus and method is executed in consideration of one l × n matrix obtained by concatenating the matrices representing the functions. May be.

In [Fourth Embodiment of Random Number Sequence Generating Device and Method], the probability distribution may be given as a conditional probability distribution as in [Third Embodiment of Random Number Sequence Generating Device and Method]. In this case, f _k (x _k ) is as follows.

[Fifth Embodiment of Random Number Sequence Generation Apparatus and Method]
The fourth embodiment of the random number sequence generation device and method is a random number sequence generation device and method when a constraint condition is described using a plurality of functions having different domains of definition. Below, it demonstrates centering on a different part from 1st embodiment of a random number sequence generation apparatus and method, and it abbreviate | omits duplication description about the part similar to 1st embodiment of a random number sequence generation apparatus and method.

i∈K≡ {1,2, ..., κ}, X _K ^* ≡ {X _i ⁿⁱ } _i∈K . here,
[X _i ⁿⁱ ] ≡ [X _{i, 1} ] × [X _{i, 2} ] ×… × [X _{i, n} ]
X _i ⁿⁱ ≡ (X _{i, 1} , X _{i, 2} ,…, X _{i, ni} ) ∈ [X _i ⁿⁱ ]
It is. In a random number generation method that satisfies the constraints, a set of functions with different domains Φ _i ≡ {φ _{i, s} : [X _i ⁿⁱ ] → V _{i, s} } _{s = 1} ^li
as well as
v _i ^li ≡ (v _{i, 1} , v _{i, 2} ,…, v _{i, li} ) ∈V _{i, 1} × V _{i, 2} ×… × V _{i, li}
And the distribution p_ (X _K ^* )

Random number according to

To generate

In the meantime, the specific processing of the first embodiment of the random number sequence generation apparatus and method may be executed. here,
θ _k ^* ≡ {θ _i } _i∈K
The order of arranging the random variables included in X _K ^* and x ⁿ is arbitrary. In the following, the index attached below x is the index after such rearrangement.
That is, for example, (a5) is expressed by the following equation.

Where T (i, s) ⊂ {1,2,…, n} is

^Is the set of indices at x ⁿ of the variables x _i ⁿⁱ used to calculate

It is.
Of course, if [X _i ⁿⁱ ] ∈ GF (q) ⁿⁱ and all the functions Φ _c are linear mappings (matrixes), the random number sequence is generated by considering one l × n matrix concatenating the matrices representing the functions. You may perform the specific process of 2nd embodiment of an apparatus and a method. That is, the specific processing of the second embodiment of the random number sequence generation apparatus and method can be used in consideration of an l × n matrix in which matrices are connected on a diagonal line and variable portions unrelated to the function are filled with 0. For example, when Φ ₁ and Φ ₂ can be expressed as l ₁ × n ₁ matrix and l ₂ × n ₂ matrix, respectively, the matrix expressing Φ is (l ₁ + l ₂ ) × (n ₁ + n ₂ ) matrix

It becomes. Here, O represents a zero matrix.

Also in [Fifth Embodiment of Random Number Sequence Generating Device and Method], the probability distribution may be given as a conditional probability distribution as in [Third Embodiment of Random Number Sequence Generating Device and Method]. In this case, f _k (x _k ) is as follows.

[Modification of Embodiment of Random Number Sequence Generation Apparatus and Method]
[Fourth embodiment of random number sequence generation apparatus and method] and [Fifth embodiment of random number sequence generation apparatus and method] can be combined. At this time, if there is no ^{_{u n, f k (x k}} ) is as follows.

A is when combined the fourth embodiment of the random number sequence generation apparatus and method] and [Fifth embodiment of the random number sequence generation apparatus and method, when there is ^{_{u n, f k (x k}} ) The following It becomes like this.

When combining [fourth embodiment of random number sequence generation apparatus and method] and [fifth embodiment of random number sequence generation apparatus and method], set C is determined depending on i, and l (dimension of vector v ^l ) is It depends on i and c. appearing in equation _{f k (x k) (x} 1, x 2, ..., x n) is the index of the {x _i ^ni} those arranged in the proper order to _{i∈K (x 1, x 2,} ... , corresponding to the index when the _{x n), T (i,} c, s) is (x ₁ of variables used in computing the function _{φ i, c, s, x} 2, ..., relates x _n) Represents an index. Note that n≡Σ _i∈K n _i .

[Caution about embodiment regarding channel code]
Before description of [first embodiment of encoding device and method and decoding device and method] to [fifth embodiment of encoding device and method and decoding device and method], which are embodiments relating to channel codes, these are described. A note about the embodiment related to the channel code is described.

  In the following, the base of the logarithm is unified to 2 etc., for example.

A and B generally represent functions, and A (x ⁿ ) and B (x ⁿ ) represent values in the vector x ⁿ of the functions A and B, respectively. The ranges of the functions A and B are written as ImA≡ {A (x ⁿ ): x ⁿ ∈ [X ⁿ ]} and ImB≡ {B (x ⁿ ): x ⁿ ∈ [X ⁿ ]}, respectively.

In the following embodiment, a set [A], [B] of functions having [X _n ] as a domain is considered. Im [A] and Im [B] are set as follows.

[A] and [B] are used only for describing the conditional expression, and in the encoding, functions A and B are selected one by one from [A] and [B], respectively. [X ⁿ ], ImA, ImB, Im [A], and Im [B] may or may not be a linear space. When the factor graph determined by the variable x ⁿ and the functions A and B has a sparse structure, particularly when the functions A and B are expressed by a sparse matrix, the approximation performance by the sum-product algorithm can be improved. Further, in the decoding configuration, the maximum likelihood decoding in the random number sequence estimator is approximated by using, for example, the sum-product algorithm described in References 2 and 3 or the linear programming described in References 4 and 5, for example. Can be realized.

[Reference 2] SM Aji and RJ McEliece, “The generalized distributive law,” IEEE Trans. Inform. Theory, vol. 46, no. 2, pp. 325-343, Mar. 2000.
[Reference 3] FR Kschischang, BJ Frey, and HA Loeliger, "Factor graphs and the sum-product algorithm," IEEE Transactions on Information Theory, vol. 47, no. 2, pp. 498-519, Feb. 2001.
[Reference 4] J. Feldman, MJ Wainwright, and DR Karger, “Using linear programming to decode binary linear codes,” IEEE Trans. Inform. Theory, vol. IT-51, no. 3, pp. 954-972, Mar. 2005.
[Reference 5] T. Wadayama, “An LP decoding algorithm based on primal path-following interior point method,” Proc. 2009, Int. Symp. Inform. Theory, Seoul, Korea, pp. 389-393, 2009.

When [X ⁿ ] is an n-dimensional vector space on a finite field GF (q) and the functions A and B used for encoding are matrices whose elements are values of the finite field GF (q), [A] Is a set consisting of the entire m × n matrix, and [B] is a set consisting of the entire m ′ × n matrix,

Therefore, the conditional expression regarding log | Im [A] |, log | Im [B] | that appears later can be converted into the conditional expression regarding q, n, m, m ′. A is an m-dimensional vector and b is an m′-dimensional vector.

The conditional entropy of X ⁿ when the entropy Y ⁿ random variables X ⁿ given are defined as follows.

When applying a random number sequence generation method that satisfies a constraint condition, if a random number that satisfies a constraint condition determined using a conditional probability distribution is required, [random number sequence generation apparatus and method first embodiment] to [random number sequence] The method described in the fifth embodiment of the generation apparatus and method may be applied.

“Recorded function” means that a means for calculating the function is recorded. If the function has linearity, the coefficients should be recorded in the form of a matrix. The fact that the probability distribution is recorded means that means for calculating the probability of the actual value is recorded. The means for calculating the function and the means for calculating the probability of the actual value are implemented by, for example, a program as will be described later. For example, if a parametrized continuous distribution such as a Gaussian distribution, a steady memorylessness, or a Markov property is assumed, a means for calculating a probability with a small capacity can be recorded. When a constrained random number generation algorithm is used, it can be replaced with information necessary for calculating f _k (x _k ).

[First Embodiment of Encoding Device and Method and Decoding Device and Method]
<When the coding apparatus does not observe u ^n>
Hereinafter, with reference to FIG. 4, described the configuration in which the coding device 100 does not observe the supplementary information u ⁿ of the channel 300.

  First, a rough flow of data in the present embodiment relating to communication path codes will be described.

The message b is an element of the set Im [B], and is an m′-dimensional vector when B is an m ′ × n matrix. The predetermined shared information a is an element of the set Im [A]. When A is an m × n matrix, it is an m-dimensional vector. The encoding device obtains a codeword ^{xn serving} as an input for the communication path from the messages b and a. The codeword x ⁿ ≡ (x ₁ , x ₂ ,..., X _n ) is an element of the set [X ⁿ ].

X ⁿ input to the communication path changes under the influence of noise or the like, and is output from the communication path as y ⁿ . Here, the output y ⁿ ≡ (y ₁ ,..., Y _n ) of the communication path is an element of the set [Y ⁿ ]. Decoding apparatus obtains the estimated value β of the message b from y ⁿ and a. β is an element of Im [B].

  As illustrated in FIG. 4, the encoding device 100 includes, for example, a random number sequence generation device 1 and a storage unit 101. The decoding device 200 includes, for example, a storage unit 201, a random number sequence estimation unit 202, and a message estimation unit 203. The encoding device 100 and the decoding device 200 are connected by a communication path 300.

In the storage unit 101, functions A and B, predetermined shared information a, and probability distribution p _X ⁿ are recorded. The random number sequence generation device 1 reads the recorded information from the storage unit 101 as necessary, and performs the processing described later.

In the storage unit 201, functions A and B, predetermined shared information a, and probability distribution p _X ⁿ _{| Y} ⁿ are recorded. The information recorded in the storage unit 201 is set in advance by an administrator or the like according to the nature of the communication path 300. The random number sequence estimation unit 202 and the message estimation unit 203 read the recorded information from the storage unit 201 as necessary, and perform processing described later.

  Here, [A] and [B] are set so as to satisfy the following relationship.

Let x ⁿ ∈ [X ⁿ ], y ⁿ ∈ [Y ⁿ ]. ^Let p _Y ⁿ _{| X} ⁿ be the probability distribution that characterizes the communication path 300. The input distribution p _X ⁿ is a design parameter and can be arbitrarily given. Usually, a value having a large (H (X ⁿ ) −H (X ⁿ | Y ⁿ )) is given. Here, P _Y ⁿ (y ⁿ ) and P _X ⁿ _{| Y} ⁿ (x ⁿ | y ⁿ ) are defined as follows.

Message b is input to random number sequence generation device 1 of encoding device 100.

The random number sequence generation device 1 generates a random number sequence x ⁿ according to the following probability distribution μ for the message bεIm [B] and the predetermined shared information aεIm [A], and encodes it. Is input to the communication path 300 as a code word that is an output of (Step Be1, FIG. 1).

Here, in step Be1, one selected from a plurality of random number sequences generated according to the probability distribution μ may be selected as x ⁿ .

When the predetermined condition is Ax ⁿ = a, Bx ⁿ = b as described above, the random number sequence generation device 1
Im [A] ⊂V _1,1 × V _1,2 ×… × V _{1, m}
Im [B] ⊂V _2,1 × V _2,2 ×… × V _{2, m '}
Set satisfy _{V 1,1, V 1,2, ...,} V 1, m, V 2,1, ..., assuming that there is V _{2, m ',} based on the following definition [random number sequence By applying the method described in the fourth embodiment of the generation apparatus and method, a sequence of random numbers x ⁿ can be generated, for example.

The output y ⁿ of the channel 300 is input to the random number sequence estimating unit 202 of the decoding device 200.

The random number sequence estimation unit 202 obtains an estimated value ξ ⁿ of x ⁿ defined by the following equation from the output y ⁿ of the communication path 300 (step Bd1, FIG. 11). The obtained ξ ⁿ is transmitted to the message estimation unit 203.

Instead of obtaining (b1), ξ ⁿ is approximately obtained using, for example, the sum-product algorithm described in References 2 and 3 or the linear programming described in References 4 and 5, for example. May be.

As described above, the random number sequence estimation unit 202 uses the output y ⁿ of the communication channel 300 as a condition among a plurality of value series θ ⁿ satisfying the predetermined function A when the predetermined shared information a is given. theta ⁿ is seeking theta ⁿ that maximizes the probability of occurrence as xi] ^n, to estimate the sequence xi] ⁿ of Motoma' values as a sequence x ⁿ of random numbers was output of the random number sequence generating device 1 when.

The message estimation unit 203 obtains an estimated value β of the message by calculating β≡B (ξ ⁿ ) (step Bd2). In this way, the message estimation unit 203 uses the predetermined function B to generate the estimated value β of the message from the estimated random number sequence ξ ⁿ .

In addition, when A and B are linear mappings, that is, a matrix, the random number sequence generation device 1 considers an (m + m ′) × n matrix obtained by concatenating the matrices, and [the second implementation of the random number sequence generation device and method] The random number sequence x ⁿ may be generated by applying the method described in the embodiment.

  A specific example is described below. The function A is expressed as an m × n matrix and the function B is expressed as an m ′ × n matrix as follows.

  Assuming that the matrices A and B are full rank, an m-dimensional vector a and an m′-dimensional vector b representing a message are expressed as follows.

Let the function Φ be an (m + m ′) × n matrix as follows, and let l≡m + m ′ be a vector v ^l as follows:

The probability distribution p _X ⁿ on [X ⁿ ] is determined, and the encoding apparatus 100 inputs the random number x ⁿ generated with the distribution μ determined by (a2) to the communication path 300. Where Φ (θ _n ) = v ^l is

The decoding apparatus receiving the communication path 300 output y ⁿ seeking an estimate xi] ⁿ of x ⁿ by (b1), the β is m 'dimensional vector and the estimated value of the message.

Here, the conditional expression A (θ ⁿ ) = a is as follows.

  Hereinafter, another specific example will be described.

Assume that q = 2, n = 7, and [X ⁿ ] ≡GF (2) ⁷ and [Y ⁿ ] ≡GF (2) ⁷ . The communication channel probability distribution is assumed as follows.

Here, ζ is a real number between 0 and 1. The probability distribution p _X ⁿ on [X ⁿ ] is determined as follows.

The probability distribution p _X ⁿ _{| Y} ⁿ is given by

The probability distribution p_ (X _t | X ₁ ^t−1 ) is given by

  Here, η is a real number between 0 and 1. Assuming that ζ = 1/4 and η = 5/7, the result is as follows.

  Assuming that functions A and B are matrices and the number of columns is m = 3 and m ′ = 2, the following equations are satisfied.

  Here, the base of the logarithm is 2.

  The 3 × 7 matrix A and the 2 × 7 matrix B are defined as follows.

  A three-dimensional vector a is defined as follows.

  Now encode the following two-dimensional vector representing the message.

  Function Φ is a 5 × 7 matrix

And let v≡m + m ′ = 5 and define the vector v ^l as follows:

In generating a random number sequence according to the method described in [Second Embodiment of Random Number Sequence Generation Apparatus and Method], Ψ ₁ and Ψ ₂ are determined as follows.

Since Ψ ₂ is a regular matrix, the inverse matrix Ψ ₂ ⁻¹ is as follows.

  Here, the specific processing of the random number generation device of [second embodiment of random number sequence generation device and method] is performed.

1. In step A1, k = 1 is set. v _s (1) is as follows.

2. In step A2, T (s, 1), χ (xT _{(s, 1)} , v _s (1)) is as follows.

function

By calculating

Get.

  3. Probability distribution in step A3

Generate a random number 0 or 1. Assuming that 0 is generated below, x ₁ = 0.

4. In step A4, k = 2. v _s (2) is as follows.

  Then, the process returns to step A2.

5. In step A2, T (s, 2), χ (xT _{(s, 2)} , v _s (2)) is as follows.

  function

By calculating

Get.
6. Probability distribution in step A3

Generate a random number 0 or 1. Assuming that 1 is generated below, x ₂ = 1.

7. In step A6, v _s (3) is as follows.

Here, (x ₃ ,..., X ₇ ) is obtained as follows.

The random number sequence generator outputs x ⁿ = (0,1,0,0,1,1,1) and ends.

The encoding device inputs the output x ⁿ = (0,1,0,0,1,1,1) of the random number generator to the communication path as a code word.

In the following, it is assumed that the output of the communication path is y ⁿ = (0,1,0,1,1,1,1). The decoding device that receives the output y ^{n of the} communication channel first estimates x ⁿ

As a result of seeking

Get. Next, the estimated value of the message in the message estimation unit

Get.
<When encoder observes u ^n>
In the following, with reference to FIG. 5, the channel 300 has two inputs w ⁿ and u ^n, describes the configuration in which the coding device 100 observes u ^n.

  First, a rough flow of data in the present embodiment relating to communication path codes will be described.

The output x ⁿ ≡ (x ₁ , x ₂ ,..., X _n ) of the random number sequence generation device 1 is an element of the set [X ⁿ ]. The channel input u ⁿ ≡ (u ₁ ,..., U _n ) is an element of the set [U ⁿ ].

The message b is an element of the set Im [B], and is an m′-dimensional vector when B is an m ′ × n matrix. The predetermined shared information a is an element of the set Im [A]. When A is an m × n matrix, it is an m-dimensional vector. Encoding apparatus obtains the codeword w ⁿ as an input communication path and a message b and a and u ^n, input to the channel. The codeword w ⁿ ≡ (w ₁ ,..., W _n ) is an element of the set [W ⁿ ]. W ⁿ input to the communication path changes under the influence of noise or the like and is output from the communication path as y ⁿ . Here, the output y ⁿ ≡ (y ₁ ,..., Y _n ) of the communication path is an element of the set [Y ⁿ ]. Assume that the set [Y ⁿ ] is not necessarily a finite set. Decoding apparatus obtains the estimated value β of the message b from y ⁿ and a. β is an element of Im [B].

  As illustrated in FIG. 5, the encoding device 100 includes, for example, a random number sequence generation device 1, a storage unit 101, and a conversion filter unit 102. The decoding device 200 includes, for example, a storage unit 201, a random number sequence estimation unit 202, and a message estimation unit 203. The encoding device 100 and the decoding device 200 are connected by a communication path 300.

In the storage unit 101, functions A and B, predetermined shared information a, and probability distributions p _X ⁿ _{| U} ⁿ and p _W ⁿ _{| X} ⁿ _U ⁿ are recorded. The random number sequence generation device 1 and the conversion filter unit 102 read these recorded information from the storage unit 101 as necessary, and perform processing described later.

In the storage unit 201, functions A and B, predetermined shared information a, and probability distribution p _X ⁿ _{| Y} ⁿ are recorded. The information recorded in the storage unit 201 is set in advance by an administrator or the like according to the nature of the communication path 300. The random number sequence estimation unit 202 and the message estimation unit 203 read the recorded information from the storage unit 201 as necessary, and perform processing described later.

  Here, [A] and [B] are set so as to satisfy the following relationship.

Let x ⁿ ∈ [X ⁿ ], y ⁿ ∈ [Y ⁿ ], u ⁿ ∈ [U ⁿ ], w ⁿ ∈ [W ⁿ ]. The probability distribution that characterizes the communication path 300 is assumed to be p _U ⁿ , p _Y ⁿ _{| W} ⁿ _U ⁿ . The conditional probability distribution p _W ⁿ _{| X} ⁿ _U ⁿ , p _X ⁿ _{| U} ⁿ is a design parameter and can be given arbitrarily, but usually (H (X ⁿ | U ⁿ ) -H (X ⁿ | Y ⁿ )) gives a large one. Here, P _Y ⁿ (y ⁿ ) and P _X ⁿ _{| Y} ⁿ (x ⁿ | y ⁿ ) are defined as follows.

Message b and u ⁿ are input to the random number sequence generating device 1 of the encoding apparatus 100.

The random number sequence generation device 1 generates a random number sequence x ⁿ according to the following probability distribution μ for the message bεIm [B], the input u ⁿ of the communication path 300 and the predetermined shared information aεIm [A]. (Step Be1, FIG. 10). The random number sequence x ⁿ is transmitted to the conversion filter unit 102.

Here, in step Be1, one selected from a plurality of random number sequences generated according to the probability distribution μ may be selected as x ⁿ .

When the predetermined condition is Ax ⁿ = a, Bx ⁿ = b as described above, the random number sequence generation device 1
Im [A] ⊂V _1,1 × V _1,2 ×… × V _{1, m}
Im [B] ⊂V _2,1 × V _2,2 ×… × V _{2, m '}
Set satisfy _{V 1,1, V 1,2, ...,} V 1, m, V 2,1, ..., assuming that there is V _{2, m ',} based on the following definition [random number sequence By applying the method described in the third embodiment of the generation device and method and the fourth embodiment of the random number sequence generation device and method, the random number sequence x ⁿ can be generated, for example.

The transform filter unit 102 encodes a sequence w ⁿ ≡F (x ⁿ , u ⁿ ) obtained through a random or deterministic transform F according to the probability distribution p _W ⁿ _{| X} ⁿ _U ⁿ as an output of the encoding device 100. A word is input to the communication path 300 (step Be2).

The output y ⁿ of the channel 300 is input to the random number sequence estimating unit 202 of the decoding device 200.

The random number sequence estimation unit 202 obtains an estimated value ξ ⁿ of x ⁿ defined by the following equation from the output y ⁿ of the communication path 300 (step Bd1, FIG. 11). The obtained ξ ⁿ is transmitted to the message estimation unit 203.

Instead of obtaining ξ ⁿ from the above formula, ξ ⁿ is approximated using, for example, the sum-product algorithm described in References 2 and 3 or the linear programming described in References 4 and 5, for example. You may ask for.

As described above, the random number sequence estimation unit 202 uses the output y ⁿ of the communication channel 300 as a condition among a plurality of value series θ ⁿ satisfying the predetermined function A when the predetermined shared information a is given. theta ⁿ is seeking theta ⁿ that maximizes the probability of occurrence as xi] ^n, to estimate the sequence xi] ⁿ of Motoma' values as a sequence x ⁿ of random numbers was output of the random number sequence generating device 1 when.

The message estimation unit 203 obtains an estimated value β of the message by calculating β≡B (ξ ⁿ ) (step Bd2). In this way, the message estimation unit 203 uses the predetermined function B to generate the estimated value β of the message from the estimated random number sequence ξ ⁿ .

[Second Embodiment of Encoding Device and Method and Decoding Device and Method]
6 and 7, the communication channel 300 has one input w ⁿ and two outputs y ⁿ and z ^n, and configures a code for an eavesdropping communication channel in which an eavesdropper observes z ^n. A second embodiment of the encoding apparatus and method and the decoding apparatus and method will be described.

<When the coding apparatus does not observe u ^n>
First, referring to FIG. 6, described the configuration in which the coding device 100 does not observe the supplementary information u ⁿ of the channel 300.

  A general flow of data in the embodiment relating to the communication path code will be described.

The output x ⁿ ≡ (x ₁ , x ₂ ,..., X _n ) of the random number sequence generation device 1 is an element of the set [X ⁿ ].

The message b is an element of the set Im [B], and is an m′-dimensional vector when B is an m ′ × n matrix. The predetermined shared information a is an element of the set Im [A]. When A is an m × n matrix, it is an m-dimensional vector. Encoding apparatus obtains the codeword w ⁿ as a communication channel of the input from the message b and a, is input to the communication path. The codeword w ⁿ ≡ (w ₁ ,..., W _n ) is an element of the set [W ⁿ ].

W ⁿ input to the communication path changes under the influence of noise or the like and is output from the communication path as y ⁿ . Here, the output y ⁿ ≡ (y ₁ ,..., Y _n ) of the communication path is an element of the set [Y ⁿ ]. Decoding apparatus obtains the estimated value β of the message b from y ⁿ and a. β is an element of Im [B]. Decoding apparatus obtains the estimated value β of the message b from y ⁿ and a. β is an element of Im [B].

Further, the third party eavesdrops on the communication path to obtain information z ⁿ as the output of the communication path. The channel output z ⁿ ≡ (z ₁ ,..., Z _n ) is an element of the set [Z ⁿ ].

  As illustrated in FIG. 6, the encoding device 100 includes, for example, a random number sequence generation device 1, a storage unit 101, and a conversion filter unit 102. The decoding device 200 includes, for example, a storage unit 201, a random number sequence estimation unit 202, and a message estimation unit 203. The encoding device 100 and the decoding device 200 are connected by a communication path 300.

In the storage unit 101, functions A and B, predetermined shared information a, and probability distributions p _X ⁿ and p _W ⁿ _{| X} ⁿ are recorded. The random number sequence generation device 1 and the conversion filter unit 102 read these recorded information from the storage unit 101 as necessary, and perform processing described later.

In the storage unit 201, functions A and B, predetermined shared information a, and probability distribution p _X ⁿ _{| Y} ⁿ are recorded. The information recorded in the storage unit 201 is set in advance by an administrator or the like according to the nature of the communication path 300. The random number sequence estimation unit 202 and the message estimation unit 203 read the recorded information from the storage unit 201 as necessary, and perform processing described later.

  Here, [A] and [B] are set so as to satisfy the following relationship.

^{Here, H (X n | Z n} ) , the following _{^{p Z n (z n),}} p X n | Z n | defined by (x ⁿ z ^n).

Let x ⁿ ∈ [X ⁿ ], y ⁿ ∈ [Y ⁿ ], z ⁿ ∈ [Z ⁿ ], w ⁿ ∈ [W ⁿ ]. The probability distribution that characterizes the communication path 300 is defined as p _Y ⁿ _Z ⁿ _{| W} ⁿ . The distribution p _X ⁿ , p _W ⁿ _{| X} ⁿ is a design parameter and can be given arbitrarily, but usually gives a large value of (H (X ⁿ | Z ⁿ ) -H (X ⁿ | Y ⁿ )) .

Message b is input to random number sequence generation device 1 of encoding device 100.

The random number sequence generation device 1 generates a random number sequence x ⁿ according to the following probability distribution μ for the message bεIm [B] and the predetermined shared information aεIm [A] (step Be1, FIG. 10). . The random number sequence x ⁿ is transmitted to the conversion filter unit 102.

Here, in step Be1, one selected from a plurality of random number sequences generated according to the probability distribution μ may be selected as x ⁿ .

When the predetermined condition is Ax ⁿ = a, Bx ⁿ = b as described above, the random number sequence generation device 1
Im [A] ⊂V _1,1 × V _1,2 ×… × V _{1, m}
Im [B] ⊂V _2,1 × V _2,2 ×… × V _{2, m '}
Set satisfy _{V 1,1, V 1,2, ...,} V 1, m, V 2,1, ..., assuming that there is V _{2, m ',} based on the following definition [random number sequence By applying the method described in the third embodiment of the generation apparatus and method, a sequence of random numbers x ⁿ can be generated, for example.

The transform filter unit 102 uses the sequence w ⁿ ≡F (x ⁿ ) obtained through a random or deterministic transform F according to the probability distribution p _W ⁿ _{| X} ⁿ as a code word that is an output of the encoding device 100, as a communication channel 300. (Step Be2).

The output y ⁿ of the channel 300 is input to the random number sequence estimating unit 202 of the decoding device 200.

The random number sequence estimation unit 202 obtains an estimated value ξ ⁿ of x ⁿ defined by the following equation from the output y ⁿ of the communication path 300 (step Bd1, FIG. 11). The obtained ξ ⁿ is transmitted to the message estimation unit 203.

Instead of obtaining ξ ⁿ by the above formula, ξ ⁿ is approximated using, for example, the sum-product algorithm described in References 2 and 3 or the linear programming described in References 4 and 5, for example. You may ask for.

As described above, the random number sequence estimation unit 202 uses the output y ⁿ of the communication channel 300 as a condition among a plurality of value series θ ⁿ satisfying the predetermined function A when the predetermined shared information a is given. theta ⁿ is seeking theta ⁿ that maximizes the probability of occurrence as xi] ^n, to estimate the sequence xi] ⁿ of Motoma' values as a sequence x ⁿ of random numbers was output of the random number sequence generating device 1 when.

The message estimation unit 203 obtains an estimated value β of the message by calculating β≡B (ξ ⁿ ) (step Bd2). In this way, the message estimation unit 203 uses the predetermined function B to generate the estimated value β of the message from the estimated random number sequence ξ ⁿ .

<When encoder observes u ^n>
In the following, with reference to FIG. 7, the channel 300 has two inputs w ⁿ and u ^n, describes the configuration in which the coding device 100 observes u ^n. Here, the eavesdropper is assumed that you can not observe the u ^n.

The output x ⁿ ≡ (x ₁ , x ₂ ,..., X _n ) of the random number generation device 1 is an element of the finite set [X ⁿ ]. The input u ⁿ ≡ (u ₁ ,..., U _n ) of the communication path is an element of the set [U ⁿ ].

The message b is an element of the set Im [B], and is an m′-dimensional vector when B is an m ′ × n matrix. The predetermined shared information a is an element of the set Im [A]. When A is an m × n matrix, it is an m-dimensional vector. Encoding apparatus obtains the codeword w ⁿ as an input communication path and a message b and a and u ^n, input to the channel. The codeword w ⁿ ≡ (w ₁ ,..., W _n ) is an element of the set [W ⁿ ].

W ⁿ input to the communication path changes under the influence of noise or the like and is output from the communication path as y ⁿ . Here, the output y ⁿ ≡ (y ₁ ,..., Y _n ) of the communication path is an element of the set [Y ⁿ ]. Decoding apparatus obtains the estimated value β of the message b from y ⁿ and a. β is an element of Im [B].

Further, the third party eavesdrops on the communication path to obtain information z ⁿ as the output of the communication path. The channel output z ⁿ ≡ (z ₁ ,..., Z _n ) is an element of the set [Z ⁿ ].

  As illustrated in FIG. 7, the encoding device 100 includes, for example, a random number sequence generation device 1, a storage unit 101, and a conversion filter unit 102. The decoding device 200 includes, for example, a storage unit 201, a random number sequence estimation unit 202, and a message estimation unit 203. The encoding device 100 and the decoding device 200 are connected by a communication path 300.

In the storage unit 101, functions A and B, predetermined shared information a, and probability distributions p _X ⁿ _{| U} ⁿ and p _W ⁿ _{| X} ⁿ _U ⁿ are recorded. The random number sequence generation device 1 and the conversion filter unit 102 read these recorded information from the storage unit 101 as necessary, and perform processing described later.

In the storage unit 201, functions A and B, predetermined shared information a, and probability distribution p _X ⁿ _{| Y} ⁿ are recorded. The information recorded in the storage unit 201 is set in advance by an administrator or the like according to the nature of the communication path 300. The random number sequence estimation unit 202 and the message estimation unit 203 read the recorded information from the storage unit 201 as necessary, and perform processing described later.

  Here, [A] and [B] are set so as to satisfy the following relationship.

^{Here, H (X n | Z n} ) , the following _{^{p Z n (z n),}} p X n | Z n | defined by (x ⁿ z ^n).

Let x ⁿ ∈ [X ⁿ ], y ⁿ ∈ [Y ⁿ ], z ⁿ ∈ [Z ⁿ ], u ⁿ ∈ [U ⁿ ], w ⁿ ∈ [W ⁿ ]. The probability distribution that characterizes the channel is assumed to be p _U ⁿ , p _Y ⁿ _Z ⁿ _{| W} ⁿ _U ⁿ . The conditional probability distribution p _W ⁿ _{| X} ⁿ _U ⁿ , p _X ⁿ _{| U} ⁿ is a design parameter and can be given arbitrarily, but usually (min {H (X ⁿ | U ⁿ ), H (X ⁿ | Z ⁿ )}-H (X ⁿ | Y ⁿ )) is large. Here, P _Y ⁿ (y ⁿ ) and P _X ⁿ _{| Y} ⁿ (x ⁿ | y ⁿ ) are defined as follows.

Message b and u ⁿ are input to the random number sequence generating device 1 of the encoding apparatus 100.

The random number sequence generation device 1 generates a random number sequence x ⁿ according to the following probability distribution μ for the message bεIm [B], the input u ⁿ of the communication path 300 and the predetermined shared information aεIm [A]. (Step Be1, FIG. 10). The random number sequence x ⁿ is transmitted to the conversion filter unit 102.

Here, in step Be1, one selected from a plurality of random number sequences generated according to the probability distribution μ may be selected as x ⁿ .

When the predetermined condition is Ax ⁿ = a, Bx ⁿ = b as described above, the random number sequence generation device 1
Im [A] ⊂V _1,1 × V _1,2 ×… × V _{1, m}
Im [B] ⊂V _2,1 × V _2,2 ×… × V _{2, m '}
Set satisfy _{V 1,1, V 1,2, ...,} V 1, m, V 2,1, ..., assuming that there is V _{2, m ',} based on the following definition [random number sequence By applying the method described in the third embodiment of the generation device and method and the fourth embodiment of the random number sequence generation device and method, the random number sequence x ⁿ can be generated, for example.

The transform filter unit 102 encodes a sequence w ⁿ ≡F (x ⁿ , u ⁿ ) obtained through a random or deterministic transform F according to the probability distribution p _W ⁿ _{| X} ⁿ _U ⁿ as an output of the encoding device 100. A word is input to the communication path 300 (step Be2).

The output y ⁿ of the channel 300 is input to the random number sequence estimating unit 202 of the decoding device 200.

The random number sequence estimation unit 202 obtains an estimated value ξ ⁿ of x ⁿ defined by the following equation from the output y ⁿ of the communication path 300 (step Bd1, FIG. 11). The obtained ξ ⁿ is transmitted to the message estimation unit 203.

Instead of obtaining ξ ⁿ by the above formula, ξ ⁿ is approximated using, for example, the sum-product algorithm described in References 2 and 3 or the linear programming described in References 4 and 5, for example. You may ask for.

As described above, the random number sequence estimation unit 202 uses the output y ⁿ of the communication channel 300 as a condition among a plurality of value series θ ⁿ satisfying the predetermined function A when the predetermined shared information a is given. theta ⁿ is seeking theta ⁿ that maximizes the probability of occurrence as xi] ^n, to estimate the sequence xi] ⁿ of Motoma' values as a sequence x ⁿ of random numbers was output of the random number sequence generating device 1 when.

The message estimation unit 203 obtains an estimated value β of the message by calculating β≡B (ξ ⁿ ) (step Bd2). In this way, the message estimation unit 203 uses the predetermined function B to generate the estimated value β of the message from the estimated random number sequence ξ ⁿ .

If there is a risk that u ⁿ is observed by an eavesdropper may be replaced by a formula below (b2).

^{Here, H (X n | Z n} , U n) , the following _{^{p Z n (z n),}} p X n | Z n | defined by (x ⁿ z ^n).

The conditional probability distribution p _W ⁿ _{| X} ⁿ _U ⁿ , p _X ⁿ _{| U} ⁿ is a design parameter and can be arbitrarily given, but usually (H (X ⁿ | Z ⁿ , U ⁿ ) -H (X ⁿ | Y ⁿ )) is given.

[Third embodiment of encoding apparatus and method and decoding apparatus and method]
The kappa and one or more predetermined integer, K≡ {0,1, ..., κ }, i∈K, x i n ≡ (x i, 1, x i, 2, ..., x i, n), x _K ⁿ ≡ {x _i ⁿ } _i∈K , X _i ⁿ ≡ (X _{i, 1} , X _{i, 2} ,..., X _{i, n} ), X _K ⁿ ≡ {X _i ⁿ } _i∈K . Referring to FIG. 8, an encoding device in which channel 300 constitutes a code for a so-called multiple access channel having κ inputs x _K ⁿ ≡ {x _i ⁿ } _iεK and one output y ^n. And a third embodiment of the decoding apparatus and method will be described.

<When the encoding device and the decoding device do not share u ⁿ >
First, referring to FIG. 8, the encoding device 100-i and the decoding apparatus 200 will be described the configuration in which not share auxiliary information u ^n.

The message b _i is an element of the set Im [B _i ], and is an m ′ _i- dimensional vector when B _i is an m ′ _i × n matrix. The predetermined shared information a _i is an element of the set Im [A _i ], and if A _i is a m _i × n matrix, it is a mi _i- dimensional vector. The encoding device obtains a code word x _i ^{n serving} as an input to the communication path from the messages b _i and a _i . The codeword x _i ⁿ ≡ (x _{i, 1} , x _{i, 2} ,..., X _{i, n} ) is an element of the set [X _i ⁿ ].

X _K ⁿ input to the communication path changes under the influence of noise or the like and is output from the communication path as y ⁿ . Here, the output y ⁿ ≡ (y ₁ ,..., Y _n ) of the communication path is an element of the set [Y ⁿ ]. The decoding device obtains an estimated value β _i of the message b _i from y ⁿ and a _i . β _i is an element of Im [B _i ].

  As illustrated in FIG. 8, for iεK, the encoding device 100-i includes, for example, a random number sequence generation device 1-i and a storage unit 101-i. The decoding device 200 includes, for example, a storage unit 201, a random number sequence estimation unit 202, and a message estimation unit 203. The encoding device 100-i and the decoding device 200 are connected by a communication path 300.

As I∈K, the storage unit 101-i, the function A _i, and B _i, and a predetermined shared information a _i, the probability distribution p _Xi ⁿ are recorded. As iεK, the random number sequence generation device 1-i reads the recorded information from the storage unit 101-i as necessary, and performs the process described later.

In the storage unit 201, functions {A _i } _i∈K , {B _i } _i∈K , predetermined shared information {a _i } _i∈K , and probability distribution p _XK ⁿ _{| Y} ⁿ are recorded. . The random number sequence estimation unit 202 and the message estimation unit 203 read the recorded information from the storage unit 201 as necessary, and perform processing described later.

Here, [A _K ] ≡ {[A _i ]} _i∈K , [B _K ] ≡ {[B _i ]} _i∈K is the following relation to any i∈K and I⊂K Set to satisfy. X _I ⁿ ≡ {X _i ⁿ } _i∈I , and K \ I represents a difference set, that is, a set of elements included in K but not included in I.

H (X _I ⁿ | Y ⁿ , X _{K \ I} ⁿ ) is _expressed as p _Y ⁿ _{XK \ I} ⁿ (y ⁿ , x ^{n k} _{\ I} ), p _XI ⁿ _{| Y} ⁿ _{XK \ I} ⁿ ( x _I ⁿ | y ⁿ , x _{K \ I} ⁿ ). The subscript x _I ⁿ of Σ is the sum of moving all possible values of x _I ⁿ ≡ {x _i ⁿ } _i∈I .

Let x _i ⁿ ∈ [X _i ⁿ ], y ⁿ ∈ [Y ⁿ ]. ^Let p _Y ⁿ _{| XK} ⁿ be the probability distribution that characterizes the channel. {p _Xi ⁿ } _i∈K can be arbitrarily given as a design parameter, but usually, one that can increase | Im [B _i ] | Here, P _Y ⁿ (y ⁿ ) and P _XK ⁿ _{| Y} ⁿ (x ⁿ _K | y ⁿ ) are defined as follows. The subscript x _K ⁿ of Σ is the sum of moving all possible values of x _K ⁿ ≡ {x _i ⁿ } _i∈K .

As iεK, the message b _i is input to the random number sequence generation device 1-i of the encoding device 100-i.

As iεK, the random number sequence generation device 1-i generates a random number sequence x according to the following probability distribution μ with respect to the message b _i εIm [B _i ] and predetermined shared information a _i εIm [A _i ]. _i ⁿ is generated and input to the communication path 300 as a code word which is an output of the encoding device 100-i (step Be1, FIG. 10).

Here, in step Be1, it may be the x _i ⁿ that selects one from among obtained by a plurality generate a sequence of random numbers according to the probability distribution mu.

In this way, the random number sequence generation device 1-i, when the predetermined conditions are A _i (x _i ⁿ ) = a _i , B _i (x _i ⁿ ) = b _i ,

_Suppose that there exists a set V _{i, 1,1} , V _{i, 1,2} , ..., V _{i, 1, mi} , V _{i, 2,1} , ..., V _{i, 2, m'i} that _satisfies Te, following by applying the method described in the fourth embodiment of the random number sequence generation apparatus and method] on the basis of the definition, may be a sequence x _i ⁿ of a random number for example generation.

The output y ⁿ of the channel 300 is input to the random number sequence estimating unit 202 of the decoding device 200.

Decoding apparatus 200 determines, from random number sequence estimation section 202, output y ^{n of} channel 300 and predetermined {a _i } _i∈K , x _K ⁿ ≡ {x _i ⁿ } _i∈ determining an estimated value xi] _K ⁿ and _K (step Bd1, Figure 11). The obtained ξ _K ⁿ is transmitted to the message estimation unit 203.

Instead of seeking xi] _K ⁿ the above equation, for example, the xi] _K ⁿ using linear programming method described in sum-product algorithm or example references 4 and 5 which are described in references 2 and 3 You may obtain approximately.

In this way, the random number sequence estimation unit 202 provides a sequence θ _K ⁿ of values θ _i ⁿ satisfying the predetermined function {A _i } _iεK when the predetermined shared information {a _i } _iεK is given. of the theta _K ⁿ that maximizes the probability of theta _K ⁿ appears when subject to output y ⁿ of the channel 300 obtained as xi] _K ^n, Motoma' value of sequence xi] ⁿ _K a random number sequence generator It is estimated as a random number sequence x _K ⁿ which was an output of 1. ^{_{Here, θ K n ≡ {θ i}} n} i∈K, a ^{_{ξ K n ≡ {ξ i n}} } i∈K.

The message estimation unit 203 obtains an estimated value β _i of the message by calculating β _i ≡B _i (ξ _i ⁿ ) with i∈K (step Bd2). In this way, the message estimation unit 203 generates a message estimated value β _i from the estimated random number sequence ξ _i ⁿ using a predetermined function B _i .

<When Encoder and Decoder Share u ⁿ >
Referring to FIG. 8, the encoding device 100-i and the decoding apparatus 200 will be described the configuration for shared auxiliary information u ^n.

The output x _i ⁿ ≡ (x _{i, 1} , x _{i, 2} ,..., X _{i, n} ) of the random number sequence generation device 1-i is an element of the set [X _i ⁿ ]. The shared information u ⁿ ≡ (u ₁ ,..., U _n ) is an element of the set [U ⁿ ] and is stored in advance in the storage units of the encoder and decoder.

The message b _i is an element of the set Im [B _i ], and is an m ′ _i- dimensional vector when B _i is an m ′ _i × n matrix. The predetermined shared information a _i is an element of the set Im [A _i ], and if A _i is a m _i × n matrix, it is a mi _i- dimensional vector. The encoding device obtains a code word x _i ⁿ to be input to the communication path from the messages b _i , a _i, and u ⁿ and inputs the code word x _i ⁿ to the communication path. The codeword x _i ⁿ ≡ (x _{i, 1} ,..., X _{i, n} ) is an element of the set [X ⁿ ].

X _K ⁿ input to the communication path changes under the influence of noise or the like and is output from the communication path as y ⁿ . Here, the output y ⁿ ≡ (y ₁ ,..., Y _n ) of the communication path is an element of the set [Y ⁿ ]. The decoding device obtains an estimated value β _i of the message b _i from y ⁿ and a _i . β _i is an element of Im [B _i ].

  As illustrated in FIG. 8, for iεK, the encoding device 100-i includes, for example, a random number sequence generation device 1-i and a storage unit 101-i. The decoding device 200 includes, for example, a storage unit 201, a random number sequence estimation unit 202, and a message estimation unit 203. The encoding device 100-i and the decoding device 200 are connected by a communication path 300.

As iεK, the functions A _i and B _i , the predetermined shared information a _i and u ^n, and the probability distribution p _Xi ⁿ _{| U} ⁿ are recorded in the storage unit 101-i. As iεK, the random number sequence generation device 1-i reads the recorded information from the storage unit 101-i as necessary, and performs the process described later.

The storage unit 201 includes functions {A _i } _i∈K and {B _i } _i∈K , predetermined shared information {a _i } _i∈K and u ⁿ ∈ [U ⁿ ], and a probability distribution p _XK ^n. _{| Y} ⁿ _U ⁿ is recorded. The random number sequence estimation unit 202 and the message estimation unit 203 read the recorded information from the storage unit 201 as necessary, and perform processing described later.

Here, [A _K ] ≡ {[A _i ]} _i∈K , [B _K ] ≡ {[B _i ]} _i∈K is the following relation to any i∈K and I∈K: Set to satisfy. X _I ⁿ ≡ {X _i ⁿ } _i∈I , and K \ I represents a difference set, that is, a set of elements included in K but not included in I.

H (X _I ⁿ | Y ⁿ , X _{K \ I} ⁿ , U ⁿ ) is represented by the following p _Y ⁿ _{XK \ I} ⁿ _U ⁿ (y ⁿ , x ^{n k} _{\ I} , u ⁿ ), p _XI ⁿ _{| Y} ⁿ _{XK \ I} ⁿ _U ⁿ (x _I ⁿ | y ⁿ , x _{K \ I} ⁿ , u ⁿ ) The subscript x _I ⁿ of Σ is the sum of moving all possible values of x _I ⁿ ≡ {x _i ⁿ } _i∈I .

Let x _i ⁿ ∈ [X _i ⁿ ], y ⁿ ∈ [Y ⁿ ]. ^Let p _Y ⁿ _{| XK} ⁿ be the probability distribution that characterizes the channel. p _U ⁿ , {p _Xi ⁿ _{| U} ⁿ } _i∈K can be arbitrarily given as a design parameter, but usually one that can increase | Im [B _i ] | Here, P _Y ⁿ _{| U} ⁿ (y ⁿ | u ⁿ ) and P _XK ⁿ _{| Y} ⁿ _U ⁿ (x ⁿ _K | y ⁿ , u ⁿ ) are defined as follows. The subscript x _K ⁿ of Σ is the sum of moving all possible values of x _K ⁿ ≡ {x _i ⁿ } _i∈K .

The message b _i is input to the random number sequence generation device 1-i of the encoding device 100-i.

As iεK, the random number sequence generation device 1-i causes the message b _i εIm [B _i ] and the predetermined shared information a _i εIm [A _i ] and u ⁿ ε [stored in the storage unit 101-i. For U ⁿ ], a random number sequence x _i ⁿ according to the following probability distribution μ is generated and input to the communication path 300 as a code word that is an output of the encoding device 100-i (step Be1, FIG. 10). ).

Here, in step Be1, it may be the x _i ⁿ that selects one from among obtained by a plurality generate a sequence of random numbers according to the probability distribution mu.

In this way, the random number sequence generation device 1-i, when the predetermined conditions are A _i (x _i ⁿ ) = a _i , B _i (x _i ⁿ ) = b _i ,

_Suppose that there exists a set V _{i, 1,1} , V _{i, 1,2} , ..., V _{i, 1, mi} , V _{i, 2,1} , ..., V _{i, 2, m'i} that _satisfies Te, following by applying the method described in the fourth embodiment of the random number sequence generation apparatus and method] on the basis of the definition, may be a sequence x _i ⁿ of a random number for example generation.

The output y ⁿ of the channel 300 is input to the random number sequence estimating unit 202 of the decoding device 200.

The decoding device 200 is defined by the following equation from the output y ⁿ of the communication path 300 in the random number sequence estimation unit 202 and the predetermined {a _i } _iεK and u ⁿ stored in the storage unit 201. Estimated value ξ _K ⁿ of _K ⁿ ≡ {x _i ⁿ } _i∈K is obtained (step Bd1, FIG. 11). The obtained ξ _K ⁿ is transmitted to the message estimation unit 203.

Thus, the random number sequence estimation unit 202, a predetermined when a given predetermined shared information {a _{i} i∈K} function {A _i} of theta _i ⁿ that satisfies _I∈K sequence theta of _K ⁿ of obtains the theta _K ⁿ where theta _K ⁿ to maximize the probability of occurrence when the conditions and the shared information u ⁿ stored in the output y ⁿ and the storage unit 201 of the channel 300 as xi] _K ^n, Motoma' The estimated value sequence ξ _K ⁿ is estimated as a random number sequence x _K ⁿ which was the output of the random number sequence generation device 1. ^{_{Here, θ K n ≡ {θ i}} n} i∈K, a ^{_{ξ K n ≡ {ξ i n}} } i∈K.

The message estimation unit 203 obtains an estimated value β _i of the message by calculating β _i ≡B _i (ξ _i ⁿ ) with i∈K (step Bd2). In this way, the message estimation unit 203 generates a message estimated value β _i from the estimated random number sequence ξ _i ⁿ using a predetermined function B _i .

[Fourth Embodiment of Encoding Device and Method and Decoding Device and Method]
Each of κ and λ is a predetermined integer of 1 or more. κ and λ may be the same value or different values. K≡ {0,1, ..., κ}, L≡ {0,1, ..., λ}, i∈K, j∈L. Referring to FIG. 9, an encoding device in which communication channel 300 forms a code for a so-called broadcast communication channel having one input w ⁿ and λ outputs y _L ⁿ ≡ {y _j ⁿ } _jεL , and A fourth embodiment of the method, decoding apparatus and method will be described.

Assume that jεL is a set of message indexes decoded by the decoding device 200-j as D _j ⊂K. That is, with jεL, the decoding device 200-j reproduces b _Dj ≡ {b _i } _iεDj .

<When the encoding device and the decoding device do not share u ⁿ >
First, referring to FIG. 9, the encoding apparatus 100 and decoding apparatus 200-j is described a configuration in which not share auxiliary information u ^n.

The output x _K ⁿ ≡ {x _i ⁿ } _i∈K (where x _i ⁿ ≡ (x _{i, 1} , x _{i, 2} ,..., X _{i, n} )) of the random number sequence generator 1 is a set [X _K ⁿ ] element.

The message b _i (i = 1, 2,..., K) is an element of the set Im [B _i ], and is an m ′ _i- dimensional vector when B _i is an m ′ _i × n matrix. The predetermined shared information a _i (i = 1, 2,..., K) is an element of the set Im [A _i ], and if A _i is a _mi × n matrix, it is a _mi- dimensional vector. . The encoding device _obtains a random number sequence x _K ⁿ ≡ {x _i ⁿ } _iεK from the messages {b _i } _i∈K and {a _i } _i∈K, and communicates the obtained random number series x _K ⁿ The code word w ⁿ ≡F (x _K ⁿ ) is converted into a path input, and w ⁿ is input to the communication path. w ⁿ ≡ (w ₁ , w ₂ , ..., w _n ) is an element of the set [W ⁿ ].

The communication path input w ⁿ changes under the influence of noise or the like, and is output from the communication path as y ⁿ ≡ {y _j ⁿ } _i∈L . Here, the output y _j ⁿ ≡ (y _{j, 1} ,..., Y _{j, n} ) of the communication path is an element of the set [Y _j ⁿ ]. Assume that the set [Y _j ⁿ ] is not necessarily a finite set. The decoding device 200-j _obtains an estimated value {β _i } _i∈Dj of the message {b _i } _i∈Dj from y _j ⁿ and {a _i } _i∈Dj . β _i is an element of Im [B _i ].

  As illustrated in FIG. 9, the encoding device 100 includes, for example, a random number sequence generation device 1 and a storage unit 101. As jεL, the decoding device 200-j includes, for example, a storage unit 201-j, a random number sequence estimation unit 202-j, and a message estimation unit 203-j. As jεL, the encoding device 100 and the decoding device 200-j are connected by a communication path 300.

The storage unit 101 stores functions {A _i } _i∈K and {B _i } _i∈K , predetermined shared information {a _i } _i∈K , and probability distributions p _XK ⁿ and p _W ⁿ _{| XK} ^n. It is recorded. The random number sequence generation device 1 reads the recorded information from the storage unit 101 as necessary, and performs the processing described later.

As j∈L, the storage unit 201-j has functions {A _j } _j∈Dj , {B _j } _j∈Dj , predetermined shared information {a _i } _i∈Dj , and probability distribution p _Dj ⁿ _{| Yj} ⁿ is recorded. The random number sequence estimation unit 202-j and the message estimation unit 203-j read these recorded information from the storage unit 201-j as necessary, and perform processing described later.

Here, [A _K ] ≡ {[A _i ]} _i∈K , [B _K ] ≡ {[B _i ]} _i∈K is arbitrary I⊂K, j∈L, I′⊂D _j ⊂ K is set to satisfy the following relationship. A _i and B _i have the same domain. On the other hand, i ≠ i 'when a is, (A _i, B _i) domain of the _{(A i', B i '} ) may be different from the domain of.

H (X _{I '} ⁿ | Y _j ⁿ X _{Dj \ I'} ⁿ ), H (X _I ⁿ ) is expressed by the following p_ (Y _j ⁿ X _{Dj \ I '} ⁿ ) (y _j ⁿ x _{Dj \ I ^{'n), p_ (X I}} ' n | Y j n X Dj\I 'n) (x I' n | y j n, x Dj\I 'n), determined by the ^{_{p XI n (x I n)}} .

Let x ⁿ ∈ [X ⁿ ], y _j ⁿ ∈ [Y _j ⁿ ]. ^Let p _YL ⁿ _{| W} ⁿ be the probability distribution that characterizes the channel. p _XK ⁿ and p _W ⁿ _{| XK} ⁿ can be arbitrarily given by design parameters, but usually select one that can increase | Im [B _i ] | _{^{Here, P Yi n (y i n}} ) and _{^{P XDj n | Yj n (x}} Dj n | y j n) is defined as follows.

The message b _K ≡ {b _i } _iεK (b _i εIm [B _i ]) is input to the random number sequence generation device 1 of the encoding device 100.

The random number sequence generation device 1 includes a message b _K ≡ {b _i } _i∈K (b _i ∈Im [B _i ]) and predetermined shared information {a _i } _i∈K (a _i ∈Im [A _i ]). On the other hand, a random number sequence x _K ⁿ ≡ {x _i ⁿ } _iεK according to the following probability distribution μ is generated (step Be1, FIG. 10). Sequence x _K ⁿ of the random number is sent to the conversion filter section 102.

Here, in step Be1, it may be an x _K ⁿ that selects one from among obtained by a plurality generate a sequence of random numbers according to the probability distribution mu.

In this way, the random number sequence generation device 1 is configured so that the predetermined conditions are A _i (x _i ⁿ ) = a _i , B _i (x _i ⁿ ) = b _i

_Suppose that there exists a set V _{i, 1,1} , V _{i, 1,2} , ..., V _{i, 1, mi} , V _{i, 2,1} , ..., V _{i, 2, m'i} that _satisfies By applying the method described in [Fourth Embodiment of Random Number Sequence Generation Device and Method] and [Fifth Embodiment of Random Number Sequence Generation Device and Method] based on the following definitions, the sequence of random numbers x _K For example, ⁿ can be generated.

The transform filter unit 102 uses a sequence w ⁿ ≡F (x _K ⁿ ) obtained through a random or deterministic transform F according to the probability distribution p _W ⁿ _{| XK} ⁿ as a code word that is an output of the encoding device 100 as a communication channel. 300 is input (step Be2).

As jεL, the output y _j ⁿ of the communication path 300 is input to the random number sequence estimation unit 202-j of the decoding device 200-j.

As jεL, the decoding device 200-j defines x from the output y _j ⁿ of the communication path 300 and the predetermined {a _i } _iεDj in the random number sequence estimation unit 202-j, by the following equation: Estimated value ξ _Dj ⁿ of _Dj ⁿ ≡ {x _i ⁿ } _i∈Dj is obtained (step Bd1, FIG. 11). The obtained ξ _Dj ⁿ is transmitted to the message estimation unit 203-j.

Instead of seeking xi] _Dj ⁿ the above equation, for example, the xi] _Dj ⁿ using linear programming method described in sum-product algorithm or example references 4 and 5 which are described in references 2 and 3 You may obtain approximately.

In this way, as j∈L, the random number sequence estimation unit 202-j has a value θ that satisfies the predetermined function {A _i } _i∈Dj when given predetermined shared information {a _i } _i∈Dj is given. of _i ⁿ the sequence theta _Dj ^n, determine the theta _Dj ⁿ that maximizes the probability of theta _Dj ⁿ appears when subject to output y _j ⁿ of the channel 300 as xi] _Dj ^n, series of Motoma' values ξ _Dj ⁿ is estimated as a random number sequence x _Dj ⁿ that was part of the output of the random number sequence generation device 1. ^{_{Here, θ Dj n ≡ {θ i}} n} i∈Dj, a ^{_{ξ Dj n ≡ {ξ i n}} } i∈Dj.

As jεL, the message estimation unit 203-j obtains an estimated value β _i of the message by calculating β _i ≡B _i (ξ _i ⁿ ) for each iεD _j (step Bd2). In this way, as j∈L, the message estimation unit 203 generates an estimated value β _{i of the} message from the estimated random number sequence ξ _i ⁿ using a predetermined function {B _i } _i∈Dj .

<When Encoder and Decoder Share u ⁿ >
Referring to FIG. 9, the encoding apparatus 100 and decoding apparatus 200-j is described the configuration for shared auxiliary information u ^n.

The output x _K ⁿ ≡ {x _i ⁿ } _i∈K (where x _i ⁿ ≡ (x _{i, 1} , x _{i, 2} ,..., X _{i, n} )) of the random number sequence generator 1 is a set [X _K ⁿ ] element. The shared information u ⁿ ≡ (u ₁ ,..., U _n ) is an element of the set [U ⁿ ] and is stored in advance in the storage units of the encoder and decoder. Assume that the set [U ⁿ ] is not necessarily a finite set.

The message b _i (i = 1, 2,..., K) is an element of the set Im [B _i ], and is an m ′ _i- dimensional vector when B _i is an m ′ _i × n matrix. The predetermined shared information a _i (i = 1, 2,..., K) is an element of the set Im [A _i ], and if A _i is a _mi × n matrix, it is a _mi- dimensional vector. . The encoding device _obtains a random number sequence x _K ⁿ ≡ {x _i ⁿ } _iεK from the messages {b _i } _iεK , {a _i } _iεK, and u ^n, and _obtains the obtained random number sequence x _K ⁿ is converted into a code word w ⁿ ≡F (x _K ⁿ , u ⁿ ) as a communication path input, and w ⁿ is input to the communication path. w ⁿ ≡ (w ₁ , w ₂ , ..., w _n ) is an element of the set [W ⁿ ].

W ⁿ input to the communication path changes under the influence of noise or the like, and is output from the communication path as y ⁿ ≡ {y _j ⁿ } _i∈L . Here, the output y _j ⁿ ≡ (y _{j, 1} ,..., Y _{j, n} ) of the communication path is an element of the set [Y _j ⁿ ]. The decoding device 200-j _obtains an estimated value β _i of the message {b _i } _iεDj from y _j ⁿ , {a _i } _iεDj, and u ⁿ . β _i is an element of Im [B _i ].

  As illustrated in FIG. 9, the encoding device 100 includes, for example, a random number sequence generation device 1 and a storage unit 101. As jεL, the decoding device 200-j includes, for example, a storage unit 201-j, a random number sequence estimation unit 202-j, and a message estimation unit 203-j. As jεL, the encoding device 100 and the decoding device 200-j are connected by a communication path 300.

The storage unit 101 includes functions {A _i } _i∈K and {B _i } _i∈K , predetermined shared information {a _i } _i∈K and u ⁿ ∈ [U ⁿ ], and a probability distribution p _XK ^n. _{| U} ⁿ , p _W ⁿ _{| XK} ⁿ _U ⁿ is recorded. The random number sequence generation device 1 reads the recorded information from the storage unit 101 as necessary, and performs the processing described later.

As J∈L, the storage unit 201-j, the function _{{A j} j∈Dj, {B} j} j∈Dj and predetermined shared information _{{a i}} i∈Dj and u ⁿ ∈ [U ^n] And a probability distribution p _Dj ⁿ _{| Yj} ⁿ _U ⁿ is recorded. The random number sequence estimation unit 202-j and the message estimation unit 203-j read these recorded information from the storage unit 201-j as necessary, and perform processing described later.

Here, [A _K ] ≡ {[A _i ]} _i∈K , [B _K ] ≡ {[B _i ]} _i∈K is arbitrary I 任意 K, j∈L, I'⊂D _j On the other hand, it is set so as to satisfy the following relationship. A _i and B _i have the same domain. On the other hand, i ≠ i 'when a is, (A _i, B _i) domain of the _{(A i', B i '} ) may be different from the domain of.

H (X _{I '} ⁿ | Y _j ⁿ X _{Dj \ I'} ⁿ , U ⁿ ), H (X _I ⁿ | U ⁿ ) is p_ (Y _j ⁿ X _{Dj \ I '} ⁿ U ⁿ ) (y _j ⁿ x _{Dj \ I '} ⁿ , u ⁿ ), p_ (X _I' ⁿ | Y _j ⁿ X _{Dj \ I '} ⁿ U ⁿ ) (x _I' ⁿ | y _j ⁿ , x _{Dj \ I '} ⁿ , u ⁿ ), p _XI ⁿ _U ⁿ (x _I ⁿ | u ⁿ ).

Let x ⁿ ∈ [X ⁿ ], y _j ⁿ ∈ [Y _j ⁿ ]. ^Let p _YL ⁿ _{| W} ⁿ be the probability distribution that characterizes the channel. p _U ⁿ , p _XK ⁿ _{| U} ⁿ , p _W ⁿ _{| XK} ⁿ _U ⁿ can be arbitrarily given by design parameters, but usually select one that can increase | Im [B _i ] | _{^{Here, P Yi n | U n (}} y i n | u n) and _{^{P XDj n | Yj n U n}} (x Dj n | y j n, u n) are defined as follows.

Encoding apparatus 100 message b _K ≡ the random number sequence generating device 1 of the _{{b i} i∈K (b i} ∈Im [B i]) and u ⁿ are input.

The random number sequence generation device 1 includes a message b _K ≡ {b _i } _iεK (b _i εIm [B _i ]) and predetermined shared information stored in the storage unit 101 {a _i } _iεK (a _i For εIm [A _i ]) and u ⁿ , a sequence of random numbers x _K ⁿ ≡ {x _i ⁿ } _iεK according to the following probability distribution μ is generated (step Be1, FIG. 10). Sequence x _K ⁿ of the random number is sent to the conversion filter section 102.

Here, in step Be1, it may be an x _K ⁿ that selects one from among obtained by a plurality generate a sequence of random numbers according to the probability distribution mu.

In this way, the random number sequence generation device 1 is configured so that the predetermined conditions are A _i (x _i ⁿ ) = a _i , B _i (x _i ⁿ ) = b _i

Assuming that there exists a set V _1,1 , V _1,2 , ..., V _{1, mi} , V _2,1 , ..., V _{2, m'i} that _satisfies by applying the method described in the fourth embodiment of the pattern generating apparatus and method] and [fifth embodiment of the random number sequence generation apparatus and method, capable of a sequence x _K ⁿ of random numbers for example generation.

The transform filter unit 102 outputs the sequence w ⁿ ≡F (x _K ⁿ , u ⁿ ) obtained through the random or deterministic transform F according to the probability distribution p _W ⁿ _{| XK} ⁿ _U ⁿ as the output of the encoding device 100. The code word is input to the communication path 300 (step Be2).

As jεL, the output y _j ⁿ of the communication path 300 is input to the random number sequence estimation unit 202-j of the decoding device 200-j.

As J∈L, decoding device 200-j from the output y _j ⁿ of the channel 300 stored in the storage unit 201-j and _{{a i}} i∈Dj and u ⁿ in the random number sequence estimating unit 202-j Then, an estimated value ξ _Dj ⁿ of x _Dj ⁿ ≡ {x _i ⁿ } _iεDj defined by the following equation is obtained (step Bd1, FIG. 11). The obtained ξ _Dj ⁿ is transmitted to the message estimation unit 203-j.

Instead of seeking xi] _Dj ⁿ the above equation, for example, the xi] _Dj ⁿ using linear programming method described in sum-product algorithm or example references 4 and 5 which are described in references 2 and 3 You may obtain approximately.

In this way, as j∈L, the random number sequence estimation unit 202-j has a value θ that satisfies the predetermined function {A _i } _i∈Dj when given predetermined shared information {a _i } _i∈Dj is given. of series theta _Dj ⁿ of _i ^n, the probability of theta _Dj ⁿ appears when the output y _j ⁿ and share information u ⁿ stored in the storage unit 201-j of the channel 300 with the conditions to maximize theta _Dj ⁿ is obtained as ξ _Dj ⁿ , and the obtained value sequence ξ _Dj ⁿ is estimated as a random number sequence x _Dj ⁿ which was a part of the output of the random number sequence generation device 1. ^{_{Here, θ Dj n ≡ {θ i}} n} i∈Dj, a ^{_{ξ Dj n ≡ {ξ i n}} } i∈Dj.

As jεL, the message estimation unit 203-j obtains an estimated value β _i of the message by calculating β _i ≡B _i (ξ _i ⁿ ) for each iεD _j (step Bd2). As described above, as jελ, the message estimation unit 203 generates an estimated value β _{i of the} message from the estimated random number sequence ξ _i ⁿ using a predetermined function {B _i } _iεDj .

  In the prior art according to the prior art described in References 6 to 8, the calculation time may increase exponentially as the block length n increases.

[Reference 6] J. Muramatsu and S. Miyake, “Hash property and coding theorems for sparse matrices and maximal-likelihood coding,” IEEE Trans. Inform. Theory, vol. IT-56, no. 5, pp. 2143- 2167, May 2010.
[Reference 7] J. Muramatsu and S. Miyake “Construction of codes for wiretap channel and secret key agreement from correlated source outputs based on hash property,” IEEE Trans. Inform. Theory, vol. IT-58, no. 2, pp. 671-692, Feb. 2012.
[Reference 8] J. Muramatsu and S. Miyake, “Construction of multiple access channel code based on hash property,” Proc. 2011 IEEE Int. Symp. Inform. Theory, St. Ptersburg, Russia, pp. 2274-2278, 2011.

On the other hand, in the generation of a random number sequence from [first embodiment of encoding apparatus and method and decoding apparatus and method] to [fourth embodiment of encoding apparatus and method and decoding apparatus and method], for example, If it is assumed in step A2 that the sum-product algorithm is applied and the execution is performed with O (n), and the calculation time of step A6 and step A7 is assumed to be O (n ² ), the first embodiment Each calculation time of encoding and decoding described in the second embodiment is O (n ² ). Thus, by generating a sequence of random numbers in polynomial time, each of encoding and decoding can be performed in polynomial time.

  Hereinafter, the error probability of the channel code according to [the fourth embodiment of the encoding apparatus and method and the decoding apparatus and method] from [the first embodiment of the encoding apparatus and method and the decoding apparatus and method] converges to zero. Prove that. In the following proof, [1] to [5] indicate the following documents.

[1] TM Cover and JA Thomas, “Elements of Information Theory 2nd. Ed.,” John Wiley & Sons, Inc., 2006.
[2] JL Carter and MN Wegman, “Universal classes of hash functions,” J. Comput. Syst. Sci., Vol. 18, pp. 143-154, 1979.
[3] J. Muramatsu and S. Miyake, “Hash property and coding theorems for sparse matrices and maximal-likelihood coding,” IEEE Trans. Inform. Theory, vol. IT-56, no. 5, pp. 2143 {2167, May 2010. Corrections: vol.IT-56, no.9, p. 4762, Sep. 2010.
[4] J. Muramatsu and S. Miyake, “Construction of Slepian-Wolf source code and broadcast channel code based on hash property,” available at arXiv: 1006.5271 [cs.IT], 2010.
[5] J. Muramatsu and S. Miyake, “Construction of strongly secure wiretap channel code based on hash property,” Proc. Of 2011 IEEE Int. Symp. Inform. Theory, St. Petersburg, Russia, Jul. 31-Aug. 5, 2011, pp.612-616.

  First, the hash property will be described.

1.1 Definition and Lemma Let φ be an empty set. A set of functions whose domain is [U ⁿ ] is denoted as [A]. ImA and Im [A] are defined as follows.

The sets C _A (a) and C _AB (a, b) are defined as follows.

  A random variable having a function A∈ [A] and a∈ImA are written as As and as, respectively. In formulas, As and as may be expressed using A and a in the sans serif font, respectively.

Note that a random variable whose value is an n-dimensional vector u ⁿ ∈ [U ⁿ ] is written as U ⁿ .

Definition 1. [A _n] the function A _n: a set of ^{[U n] → Im [A} n], consider the sequence _{{[A n]} n =} 1 ∞ set. [A _n] takes a p _{As, n} random variables on the sequence _{{([A n], p} As, n)} n = 1 ∞ is called ensemble. {([A _n ], p _{As, n} )} _{n = 1} ^∞ for {p _{As, n} } _{n = 1} ^∞ real sequence {α _As (n)} _{n = 1} ^∞ , {β _As (n)} _{n = 1} ^∞ , and for any n and u ⁿ ∈ [U ⁿ ]

as well as

{([A _n ], p _{As, n} )} _{n = 1} ^∞ satisfies {α _As (n), β _As (n)} _{n = 1} ^∞ -hash. Thereafter, [A], p _As , α _As , and β _As depend on n, but are omitted when n does not move.

For example, when [A] has 2-universal hash [2] and p _As is a uniform distribution on [A], {([A _n ], p _{As, n} )} _{n = 1} ^∞ is {(1,0)} _{n = 1} ^∞ -Hashes. _{{(1,0)} n = 1} ∞ is alpha _As ≡1 in any n, a string to be β _As ≡0. The hash of the ensemble of linear mapping (matrix) will be explained in the next section.

  The following lemma holds.

Lemma 1 ([4, Lemma 4]). {([A _n ], p _{As, n} )} _{n = 1} ^∞ , ({([B _n ], p _{Bs, n} )} _{n = 1} ^∞ ) {α _As (n), β _As (n)} _{n = 1} ^∞ _-An ensemble having hash properties ({α _Bs (n), β _Bs (n)} _{n = 1} ^∞ -hash properties). The function (A, B) ∈ [A] × [B] is defined as follows.

The probability distribution p _AsBs on [A] × [B] is defined as follows.

(α _AsBs , β _AsBs ) is defined as follows.

At this time, the new ensemble ([A _n ] × [B _n ], p _{AsBs, n} )} _{n = 1} ^∞ becomes {α _AsBs (n), β _AsBs (n)} _{n = 1} ^∞ _-hash Have.

Lemma 2 ([4, Lemma 1]). When ([A], p _As ) satisfies (H3), the following expression holds for any T, T′⊂ [U ⁿ ].

Lemma 3 ([3, Lemma 1]). When ([A], p _A ) satisfies (H3 ′), the following equation holds for any T ⊂ [U ⁿ ], u ⁿ ∈ [U ⁿ ].

Lemma 4 ([5, Lemma 4]). When ([A], p _As ) satisfies (H3), the following equation holds for an arbitrary function Q: [U ⁿ ] → [0, 1) and T⊂ [U ⁿ ].

  Here, Q (T) is defined as follows.

1.2 Hash properties of ensembles consisting of linear maps
^Let [U ⁿ ] ≡GF (q) ⁿ and [U ^l ] ≡GF (q) ^l . ^Let [A] be a set of linear mapping A: [U ⁿ ] → [U ^l ]. A can be expressed as an l × n matrix.

^Let t (u ⁿ ) be the type of u ⁿ ∈ [U ⁿ ] (relative frequency distribution of u ⁿ ). Let [H] be a set consisting of all types of sequences of length n except t (0 ⁿ ). S (p _As , t) is defined as follows for the probability distribution pAs and the type t∈ [H] on the set of l × n matrices.

When a set [H '] ⊂ [H] is given, α _As (n) and β _As (n) are defined as follows.

Here, p ^{表 す} represents a uniform distribution on the set of the entire l × n matrix.

Lemma 5 ([4, Theorem 1]). ([A], p _As) as a set of linear _{mapping, p As ({A: Au} n = 0 l}) depends only on ^{t (u n) (t (} u n) = t (v ⁿ ), p _As ({A: Au ⁿ = 0 ^l }) = p _As ({A: Av ⁿ = 0 ^l }). {α _As (n) defined in (B2) and (B3) , β _As (n)} _{n = 1} ^∞ satisfies (H1), (H2), {([A _n ], p _{As, n} )} _{n = 1} ^∞ is {α _As (n), β _As (n)} _{n = 1} ^{∞ -has a} hash property.

Hereinafter, U≡GF (q), 0 <R <1, and l≡nR. An l × n matrix A is generated by the following procedure.
1. Initialize all elements of the matrix with zeros.
2. Repeat the following procedure τ times for each i∈ {1, ..., n}.
(a) (j, θ) ∈ {1,..., l} × [GF (q) \ {0}] is uniformly selected.
(b) Add θ to the (j, i) -component of A (addition of GF (q)).

It is assumed that τ = O (log n) is an even number and ([A], p _As ) is determined by the above procedure. [H ′] ⊂ [H] is appropriately determined, and (α _As , β _As ) is defined by (B2) and (B3). At this time, it is proved by [3, Theorem 2] that {α _As (n), β _As (n)} _{n = 1} ^∞ satisfies (H1) and (H2) for this ensemble. Therefore, according to Lemma 5, this ensemble has {α _As (n), β _As (n)} _{n = 1} ^∞ -hash.

  Next, it is proved that the error probability of the channel code converges to 0.

A set [X ⁿ ] of channel inputs is a finite set, a set [Y ⁿ ] of channel outputs is an infinite set, and an arbitrary set including a continuous set.

Consider an ensemble of functions A: [X ⁿ ] → Im [A] and B: [X ⁿ ] → Im [B]. Here, a set of all messages is Im [B].

  In the following, it is assumed that the functions Aε [A], Bε [B], and aεIm [A] are fixed and can be used by the encoding device and the decoding device.

A random number generator that satisfies the constraint conditions is used to configure the encoding device. _{^{X ~ n ≡X ~ n AB (}} a, b) is a random variable that follows the following distribution μ a.

The encoding device Φ _n : Im [B] → [X ⁿ ] and the decoding device ψ _n : [Y ⁿ ] → Im [B] are defined as follows.

Here, when p _X ⁿ (C _AB (a, b)) = 0, the encoding device declares an encoding error. G _A is defined as follows.

The error probability Error (A, B, a) is defined as follows.

Theorem 1.

If there is an arbitrary> 0 and a sufficiently large n, there exists some A∈ [A], B∈ [B], a∈Im [A], and the following expression is satisfied.

For stationary ergodic channel p _Y ⁿ _{| X} ⁿ , p _X ⁿ

For a distribution that achieves, R is approximated by bringing nr closer to H (X ⁿ | Y ⁿ ).

You can approach.

  Proof:

And From (B9), (B10),

There exists ε> 0 that satisfies

T_ was the subscript bar T, T ^- was a superscript bar of ^{_{T, T_ X ⊂ [X n}} ], T - X | is defined ^{_{Y ⊂ [X n] × [}} Y n] as follows .

  From [1, Theorem 16.8.1], the following equation holds.

^{(x n, y n) ∈T} - X | assume ^{| (y n Ax n) ≠} x n Y, g A. At this time, θ ≠ x ⁿ and

There exists θ ⁿ ∈C _A (Ax ⁿ ) that satisfies Therefore, T ^- _{X | Y} (y ⁿ )

By defining as follows, T ⁻ _{X | Y} (y ⁿ ) ∩C _A (Ax ⁿ ) ≠ φ is satisfied. For any (x ⁿ , y ⁿ ) ∈T ⁻ _{X | Y} , the following equation holds:

Here, χ is defined as follows.

  In the second inequality, Lemma 3 and in the third inequality

Was used. Subsequently, the following formula is established.

  Here, (B18) was used in the last inequality. Moreover, the following formula | equation is materialized.

  Here, Lemma 4 is used for the second inequality. When the as distribution is a uniform distribution, the following equation holds.

  Here, in the first inequality, the following equation was used.

In the second inequality, (B19) (B20) are used. Α _As → 1, β _As → 0, α _AsBs → 1, β _AB → 0, p _X ⁿ ([T_ _X ] ^c ) by inequality (B12), (B13), (B21) and n → ∞ → 0, the ^{_{p X n Y n ([T_}} XY] c) → 0 that is true, approaches 0 the right-hand side with n → ∞ of (B21). From this, the theorem can be established.

[Modifications, etc.]
The processes described in the above apparatus and method are not only executed in time series according to the order of description, but may be executed in parallel or individually as required by the processing capability of the apparatus that executes the process.

  In addition, when the processing means in the random number sequence generation device, the encoding device, and the decoding device is realized by a computer, the processing contents of the functions that the random number sequence generation device, the encoding device, and the decoding device should have are described by a program. By executing this program on a computer, processing means in the random number sequence generation device, encoding device, and decoding device is realized on the computer.

  The program describing the processing contents can be recorded on a computer-readable recording medium. As the computer-readable recording medium, for example, any recording medium such as a magnetic recording device, an optical disk, a magneto-optical recording medium, and a semiconductor memory may be used.

  Each processing means may be configured by executing a predetermined program on a computer, or at least a part of these processing contents may be realized by hardware.

  Needless to say, other modifications are possible without departing from the spirit of the present invention.

DESCRIPTION OF SYMBOLS 1 Random number sequence generation apparatus 11 Control part 12 Probability distribution generation part 13 Random number generation part 14 Storage part 15 Random number estimation part 16 Uniform random number generation part 100 Encoding apparatus 101 Storage part 102 Transformation filter part 200 Decoding apparatus 201 Storage part 202 Random number sequence Estimating unit 203 Message estimating unit 300 Communication path

Claims (13)

The probability of an actual value that is a sequence of a plurality of values is a probability corresponding to the probability that the actual value appears in a predetermined first probability distribution, and the actual value that is a sequence of all the multiple values that satisfy a predetermined condition The probability distribution above for the second probability distribution
The third probability, which is the probability of the actual value, is the first probability that the actual value appears when the already generated random number sequence is used as the condition, the already generated random number sequence, and the currently generated random number. The distribution of the third probability for all possible realization values, with a probability corresponding to the product of the second random probability generated after the next time when the condition is satisfied and the second probability satisfying the predetermined condition A probability distribution generation unit that generates the third probability distribution, a random number generation unit that generates one real value as a random number according to the third probability distribution, and the processing of the probability distribution generation unit and the random number generation unit is repeated. A random number sequence generation device including a control unit that generates a sequence of random numbers according to the second probability distribution,
The predetermined condition is a condition expressing a relationship between the message and the predetermined shared information and the series of the plurality of values using a predetermined function.
Encoding device. The encoding device according to claim 1, comprising:
The predetermined first probability distribution is a conditional probability distribution that is conditional on a predetermined event,
The first probability and the second probability are conditional probabilities subject to the predetermined event,
Applying a conversion filter according to a predetermined fourth probability distribution on condition of the predetermined event and the random number sequence according to the second probability distribution to a random number sequence according to the second probability distribution, Further including a conversion filter unit for obtaining a series of a plurality of obtained values as input of a communication path,
Encoding device. The encoding device according to claim 1, comprising:
The predetermined function is A, B, the range of function A is Im [A], the range of function B is Im [B], the predetermined shared information is a∈Im [A], and the message is b ∈ Im [B], the series of values (x ₁ , x ₂ ,..., X _n ) is x ⁿ ∈ [X ⁿ ], and the predetermined condition is A (x ⁿ ) = a, B ( x ⁿ ) = b and the first probability distribution as p _X ⁿ
The probability for each real value x ⁿ in the second probability distribution is μ (x ⁿ ) defined by the following equation:

Encoding device. The encoding device according to claim 2, comprising:
The predetermined function is A, B, the range of function A is Im [A], the range of function B is Im [B], the predetermined shared information is a∈Im [A], and the message is b ∈ Im [B], the predetermined event as u ⁿ ∈ [U ⁿ ], the sequence of the plurality of values (x ₁ , x ₂ ,..., X _n ) as x ⁿ ∈ [X ⁿ ], and _Let p _X ⁿ _{| U} ^{n be} the first probability distribution.
The probability for each real value x ⁿ in the second probability distribution is μ (x ⁿ ) defined by the following equation:

Encoding device. The encoding device according to claim 1, comprising:
The predetermined function is A, B, the range of function A is Im [A], the range of function B is Im [B], the predetermined shared information is a∈Im [A], and the message is b ∈ Im [B], the predetermined condition is A (x ⁿ ) = a, B (x ⁿ ) = b, and the sequence of the plurality of values (x ₁ , x ₂ ,..., X _n ) is x ⁿ ∈ [X ⁿ ], and the above first probability distribution as p _X ⁿ
The probability for each real value x ⁿ in the second probability distribution is μ (x ⁿ ) defined by the following equation:

A sequence of a plurality of values is obtained by applying a transformation filter according to a predetermined fifth probability distribution on the condition of the random number sequence according to the second probability distribution to the random number sequence according to the second probability distribution. It further includes a conversion filter unit that uses a series of a plurality of values as an input to the communication path.
Encoding device. The encoding device according to claim 1, comprising:
i is an integer of 1, 2,..., κ, and the predetermined function is A _i , B _i , the range of function A _i is Im [A _i ], the range of function B _i is Im [B _i ], the predetermined shared information is a _i ∈Im [A _i ], and the message is b _i ∈ Im [B _i ], a sequence of the plurality of values (x _{i, 1} , x _{i, 2} ,..., x _{i, n} ) is x _i ⁿ ∈ [X _i ⁿ ], and the predetermined condition is A _i (x _i ⁿ ) = a _i , B _i (x _i ⁿ ) = b _i and the first probability distribution as p_ (X _i ⁿ )
The probability for each realized value x _i ⁿ in the second probability distribution is μ (x _i ⁿ ) defined by the following equation:

Encoding device. The encoding device according to claim 2, comprising:
i is an integer of 1, 2,..., κ, and the predetermined function is A _i , B _i , the range of the function A _i is Im [A _i ], the range of the function B _i is Im [B _i ], and the predetermined shared information is a _i ∈Im [A _i ], u ⁿ ∈ [U ⁿ ], the message is b _i ∈Im [B _i ], and the sequence of the plurality of values (x _{i, 1} , x _{i, 2} ,..., x _{i, n} ) is x _i ⁿ ∈ [X _i ⁿ The above predetermined condition is A _i (x _i ⁿ ) = a _i , B _i (x _i ⁿ ) = b _i, and the first probability distribution is p_ (X _i ⁿ | U ⁿ ),
The probability for each realized value x _i ⁿ in the second probability distribution is μ (x _i ⁿ ) defined by the following equation:

Encoding device. The encoding device according to claim 1, comprising:
i is an integer of 1, 2,..., κ, and the predetermined function is A _i , B _i , the range of function A _i is Im [A _i ], the range of function B _i is Im [B _i ], the predetermined shared information is a _i ∈Im [A _i ], and the message is b Let _i ∈Im [B _i ], let x _K ⁿ ≡ {x _i ⁿ } _i∈K ∈ [X _K ⁿ ], and let x _i ⁿ ≡ (x _{i, 1} , x _{i, 2} , ..., x _{i, n} ), the predetermined condition is A _i (x _i ⁿ ) = a _i , B _i (x _i ⁿ ) = b _i, and the first probability distribution is p_ (X _K ⁿ ) As
The probability for each real value x _K ⁿ in the second probability distribution is μ (x _i ⁿ ) defined by the following equation:

A sequence of a plurality of values is obtained by applying a transformation filter according to a predetermined fifth probability distribution on the condition of the random number sequence according to the second probability distribution to the random number sequence according to the second probability distribution. It further includes a conversion filter unit that uses a series of a plurality of values as an input to the communication path.
Encoding device. The encoding device according to claim 1, comprising:
i is an integer of 1, 2,..., κ, and the predetermined function is A _i , B _i , the range of the function A _i is Im [A _i ], the range of the function B _i is Im [B _i ], and the predetermined shared information is a _i ∈Im [A _i ], u ⁿ ∈ [U ⁿ ], the above message is b _i ∈Im [B _i ], the above series of values is x _K ⁿ ≡ {x _i ⁿ } _i∈K ∈ [X _K ⁿ ], and x _i ⁿ ≡ (x _{i, 1} , x _{i, 2} , ..., x _{i, n} ), the predetermined condition is A _i (x _i ⁿ ) = a _i , B _i (x _i ⁿ ) = b _i, and the first probability The distribution is p_ (X _K ⁿ ) and the first probability distribution is p_ (X _K ⁿ | U ⁿ )
The probability for each real value x _K ⁿ in the second probability distribution is μ (x _i ⁿ ) defined by the following equation:

Above for a sequence of random numbers according to the second probability distribution, the predetermined shared information u ⁿ and the second probability plurality of values by applying a conversion filter according a predetermined fourth probability distribution conditioned on sequence of random numbers according to the distribution Further including a conversion filter unit that obtains a series of a plurality of obtained values as an input of a communication path,
Encoding device. The probability of an actual value that is a sequence of a plurality of values is a probability corresponding to the probability that the actual value appears in a predetermined first probability distribution, and the actual value that is a sequence of all the multiple values that satisfy a predetermined condition The probability distribution above for the second probability distribution
The third probability, which is the probability of the actual value, is the first probability that the actual value appears when the already generated random number sequence is used as the condition, the already generated random number sequence, and the currently generated random number. The distribution of the third probability for all possible realization values, with a probability corresponding to the product of the second random probability generated after the next time when the condition is satisfied and the second probability satisfying the predetermined condition By repeating a probability distribution generation step for generating a third probability distribution, a random number generation step for generating one real value as a random number according to the third probability distribution, the probability distribution generation step and the random number generation step, A random number sequence generation step including a control step of generating a sequence of random numbers according to the second probability distribution,
The predetermined condition is a condition expressing a relationship between the message and the predetermined shared information and the series of the plurality of values using a predetermined function.
Encoding method. The encoding method of claim 1, comprising:
The predetermined first probability distribution is a conditional probability distribution that is conditional on a predetermined event,
The first probability and the second probability are conditional probabilities subject to the predetermined event,
Applying a conversion filter according to a predetermined fourth probability distribution on condition of the predetermined event and the random number sequence according to the second probability distribution to a random number sequence according to the second probability distribution, Further including a conversion filter step of obtaining a plurality of obtained values as a communication path input.
Encoding method.   A program for causing a computer to function as the encoding device according to claim 1.   A computer-readable recording medium on which a program for causing a computer to function as the encoding device according to claim 1 is recorded.

Images