tailieunhanh - Báo cáo toán học: "Zero Capacity Region of Multidimensional Run Length Constraints"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Zero Capacity Region of Multidimensional Run Length Constraints. | Zero Capacity Region of Multidimensional Run Length Constraints Hisashi Ito Department of Information Science Toho University Chiba 274-8510 Japan his@ Akiko Kato Dept. of Mathematical Engineering and Information Physics University of Tokyo Tokyo 113-8656 Japan akiko@ Zsigmond Nagy Department of Electrical and Computer Engineering University of California San Diego CA 92093-0407 nagy@ Kenneth Zeger Department of Electrical and Computer Engineering University of California San Diego CA 92093-0407 zeger@ Submitted April 24 1999 Accepted September 1 1999. 1991 Mathematics Subject Classification 94A99 58F03. 0This work was supported in part by the National Science Foundation and by a JSPS Fellowship for Young Scientists. A portion of this work was presented in Japanese at the Research Institute for Mathematical Sciences Workshop RIMS Kokyuroku Kyoto University Japan January 1999. 1 THE ELECTRONIC .JOURNAL OF COMBINATORICS 6 1999 R33 2 Abstract For integers d and k satisfying 0 d k a binary sequence is said to satisfy a one-dimensional d k run length constraint if there are never more than k zeros in a row and if between any two ones there are at least d zeros. For n 1 the n-dimensional d k -constrained capacity is defined as log2 Cdk mi W2 . mn mim2 mn where N mz . . denotes the number of mi X m2 X X mn n-dimensional binary rectangular patterns that satisfy the one-dimensional d k run length constraint in the direction of every coordinate axis. It is proven for all n 2 d 1 and k d that cdnk 0 if and only if k d 1. Also it is proven for every d 0 and k d that limn TO cdnk 0 if and only if k 2d. THE ELECTRONIC .JOURNAL OF COMBINATORICS 6 1999 R33 3 1 Introduction A binary sequence is d k -constrained or runlength constrained if there are at most k consecutive zeros and between every two ones there are at least d consecutive zeros. An n-dimensional pattern of zeros and ones arranged in an m1 X m2