The binary multiplying channel without feedback: new rate pairs in the zero-error capacity region

Two terminals, T1 and T2, wish to communicate over the binary multiplying channel (BMC). To this end, they choose sets X and Y, respectively, of (input) vectors in {0,1}ⁿ. If x∈X and y∈Y are fed to the BMC, it gives as output the vector x·y, defined by (x·y)_i=x_iy_i for all i∈{1, 2,...,n}. Each terminal should be able to determine unambiguously the vector transmitted by the other one, using its own transmitted vector and the observed channel output. We call a pair (X,Y) satisfying this requirement uniquely decodable, or UD for short. Moreover, we call a UD pair (X,Y) symmetric if X=Y. We do not allow feedback, that is, encoding of a message does not depend on the output bits observed so far. If (X,Y) is a UD pair of length n, we define the rate pair (R(X),R(Y))=(1/nlog|X|,1/nlog|Y|). As usual, all logarithms have base 2. A rate pair (x,y) will be called achievable if for each ε>O, there exists a UD pair (X,Y) such that R(X)>x-ε and R(Y)>y-ε. The set of achievable rate pairs is called the zero-error capacity region of the BMC without feedback, and it is denoted by Z. Characteristics of rate pairs are discussed