We construct linear codes over odd prime fields for correcting two-dimensional (2-D) Lee-errors on the hexagonal signal constellations. They are obtained by puncturing and enlarging either RS codes or BCH codes. We introduce 2-D Lee-weight on the hexagonal constellations in the same way as the method presented by the first author in ISIT’19, and propose an effective and efficient method for correcting Lee-errors of small weight. The concept of value-locator of an error, which was introduced implicitly by K. Nakamura in the late 1970s and early 1980s and inherited to the ISIT’19 paper, is a key for decoding Lee-error-correcting codes. Our method is based on the Buchberger algorithm for finding Gröbner bases of ideals in the multivariate polynomial ring. A result of simulations shows that our method works well for correcting Lee-errors of small weight.

A new class of double nearest-neighbor error-correcting codes on hexagonal constellation in the two dimensional space is presented. The proposed code is a linear [n,n-3] code over GF(p) where p = 6n+1 is a prime. We show that the proposed code corrects any generalized Lee error with at most weight 2.

This paper proposes two variants of improved Compression by Substring Enumeration (CSE) with a finite alphabet. In previous studies on CSE, an encoder utilizes inequalities which evaluate the number of occurrences of a substring and a minimal forbidden word (MFW) to be encoded. Also, its codeword length is proportional to the difference between the upper and lower bounds deduced from the inequalities, but the lower bound is not tight. Therefore, in this paper, we derive a new tight lower bound and consequently propose a new CSE algorithm using the new inequality. We also propose a new encoding order of substrings and MFWs which are sorted by row and column marginal totals of the proper substrings and MFWs, instead of lexicographical order used in previous studies. We then propose a new CSE algorithm which is the first proposed CSE algorithm using the new encoding order. Experimental results show that compression ratios of all files of the Calgary corpus in the proposed algorithms are better than those of a previous study on CSE with a finite alphabet. Moreover, compression ratios under the second proposed CSE get better than or equal to that under a well-known compressor for 11 files amongst 14 files in the corpus.

Rivest and Shamir introduced a write-once memory (WOM), a model of storage devices whose storage elements have restrictions on state transitions, and they presented some coding methods to reuse a WOM. An interesting question about a WOM is how efficiently we can reuse it with the best coding method, and as an answer to the question, Fu and Han Vinck determined the capacity of Fiat and Shamir's generalized WOMs. In this paper, we extend their results, introducing write-constrained memories (WCMs) that consider state transition costs, and determining the capacity of WCMs under a certain type of cost constraints.

A balanced code is a set of words over {a, b} such that the number of a's and the number of b's in a word are equal, and many applications using balanced codes have been proposed so far. Recently, not only the original balanced code, but also balanced codes with some other constraints have been studied mainly for an application of data storage media. However, contrary to other typical sets of words satisfying some constraints, the capacities of such balanced codes have not been well studied up to this moment. In this paper, we focus on balanced codes satisfying various run-length constraints and analyze their capacities. More precisely, we exhibit lower bounds on the capacities, or present the explicit capacities for certain cases.

A technique of lossless compression via substring enumeration (CSE) is a well-known lossless compression algorithm for a one-dimensional (1D) source. The CSE uses a probabilistic model built from the circular string of an input source for encoding the source. The CSE is applicable to two-dimensional (2D) sources such as images by dealing with a line of pixels of 2D source as a symbol of an extended alphabet. At the initial step of the CSE encoding process, we need to output number of occurrences of all symbols of the extended alphabet, so that the time complexity increases exponentially when the size of source becomes large. To reduce the time complexity, we propose a new CSE which can encode a 2D source in block-by-block instead of line-by-line. The proposed algorithm uses the flat torus of an input 2D source as a probabilistic model instead of the circular string of the source. Moreover, we prove the asymptotic optimality of the proposed algorithm for 2D general sources.

To formulate rewriting operations on flash memory, we extend Write-Once Memory (WOM) and introduce Erasable WOM (EWOM) which allows block erasures, and then we define codes to rewrite on them. To measure performances of EWOM codes, we introduce the rate tradeoff pair, which is derived from the sum rate. We give an outer bound of the region of the possible tradeoff pairs for a certain class of EWOM's. We also propose fixed-rate EWOM codes calledWOM2E codes that utilize existing WOM codes. It reveals that WOM2E scheme is optimal in terms of rate tradeoff pair when the block size of EWOM is “infinity.”

We propose a new class of single error correcting linear codes suitable for a two dimensional hexagonal constellation. The proposed code is a linear subspace of ℤ6n+1nwhere n is code length and 6n + 1 is a prime number. It corrects a single error in the set |±1, ±αn, ±α2n} where α is a primitive element of ℤ6n+1x. Moreover, we apply the proposed code to a two dimensional hexagonal constellation and show that it corrects an error such that a transmitted symbol moves to one of its nearest neighbors over the hexagonal constellation at the decoder side. We also consider an extension of the proposed code to double nearest neighbor error correcting codes. Some examples of such codes obtained by computer-assisted search are presented.

Antidictionaries are in particular useful for source coding. In one dimension, for an input string, there are fast construction algorithms of an antidictionary in which a suffix tree that stores all the substrings of the string is utilized. However, in two dimension (2D), for an n×n input square or rectangle, there is no fast construction algorithm of an antidictionary except a straight-forward algorithm in O(n8) time. In this paper, we propose a 2D suffix trie which stores all the subrectangles of an input rectangle and present an algorithm to construct a 2D suffix trie in O(n4log n) time. A 2D suffix trie consists of two suffix tries with suffix links rowwise and columnwise. Moreover, we propose a fast construction algorithm of a two-dimensional antidictionary using a 2D suffix trie in O(n5log n) time, and their effectivenesses are demonstrated by simulation results.

Conceptionally the User Datagram Protocol (UDP) should be well-suited for real-time applications, e.g., for Voice over IP (VoIP). However, many such applications, e.g., Skype, use the Transmission Control Protocol (TCP) either as a primary protocol or as a backup protocol when UDP is blocked, despite TCP's flow control-related data delays. This paper proposes a technique for the estimation of the application buffer requirements of such TCP-based applications and the amount of data congestion in real-time TCP data streams. We apply this technique to data collected from a global network exchanging synthetic real-time traffic over TCP. Our results show that the buffering requirements vary widely with time and path but can be substantial in many cases.

Rivest and Shamir introduced Write-Once Memory (WOM), a model of storage devices whose storage elements have restrictions on state transitions, and they presented some coding methods to reuse WOM. An interesting question about WOM is how efficiently we can reuse it with the best coding method, and as an answer to the question, Fu and Han Vinck determined the capacity of Fiat and Shamir's generalized WOM. In this paper, we extend their results, introducing Write-Constrained Memory (WCM) that considers state transition cost, and determining the capacity of WCM under a certain type of cost constraints.

Lossless data compression via substring enumeration (CSE) has been proposed by Dubé and Beaudoin in 2010. The CSE outputs its encoder called compacted substring automaton as a codeword, and an efficient representation of the automaton is also proposed. In this paper, we prove an isomorphism between compacted substring automaton and antidictionary automaton, which is an encoder of antidictionary coding. Then we propose a new static antidictionary coding which uses the representation of compacted substring automaton instead of antidictionary. Moreover, we prove an asymptotic optimality of the proposed coding for a stationary ergodic source.

An antidictionary, a set of words that never appear in a given string, is a useful data structure for source coding as well as other fields of computer sciences. A fast and memory-efficient algorithm for constructing antidictionaries by means of suffix array is presented. We prove that the proposed algorithm constructs an antidictionary array with linear time and space.

An antidictionary is in particular useful for data compression. Static construction algorithms of antidictionaries with linear complexity have been proposed. However, the construction algorithms do not work in a dynamic manner with linear complexity. In this paper, we propose a dynamic construction algorithm of an antidictionary with linear complexity. The proposed algorithm uses two linear construction algorithms of suffix trees proposed by Weiner and Ukkonen, individually. It is proved that the proposed algorithm works with linear complexity. Moreover, its effectiveness is demonstrated by simulation results.

We present new algorithms to detect and track multiple moving objects in a static surveillance video that uses MPEG-2 compression. The algorithm detects moving objects based on the location of field-based motion estimated macroblocks in inter-prediction frames, and tracks their movements along video scene by using an extension of Kalman filter that uses the objects' velocity information. Experiments show that the algorithm outputs highly accurate results in various scenarios.

An antidictionary code is a lossless compression algorithm using an antidictionary which is a set of minimal words that do not occur as substrings in an input string. The code was proposed by Crochemore et al. in 2000, and its asymptotic optimality has been proved with respect to only a specific information source, called balanced binary source that is a binary Markov source in which a state transition occurs with probability 1/2 or 1. In this paper, we prove the optimality of both static and dynamic antidictionary codes with respect to a stationary ergodic Markov source on finite alphabet such that a state transition occurs with probability p (0 <; p ≤ 1).

In this paper we propose a mutually anonymous protocol for decentralized Peer-to-Peer (P2P) networks. The protocol is a combination between the Secret-Sharing-Based Mutual Anonymity Protocol (SSMP) and the information slicing technique. The proposed protocol realizes the initiator's and responder's anonymity by using the SSMP in which the complete reply-confirm interaction between responders and initiators is realized using the information slicing algorithm. Employing the concept of secret sharing schemes plays an essential role for the protection of the transmitted information between the initiator and responder, and using the information slicing technique the proposed protocol is churn resilient and can be realized with lower cryptographic cost. Moreover, we evaluate the anonymity in the P2P system from probability point of view. The results show that the proposed mutual anonymity protocol provides higher anonymity than the conventional methods.

This paper proposes a new on-line antidictionary code with linear time. The proposed algorithm uses a subset of antidictionary which length of the elements is at most a given fixed length. It is proved that the time complexity of this algorithm is linear with respect to the string length. Its effectiveness is demonstrated by simulation results.

An error-resilient variable-length arithmetic code is presented whose codewords are represented by binary digits. The input sequence is partitioned in subsequences, each of which is individually encoded using an arithmetic coding scheme with an integrated bit-stuffing technique that restricts the number of consecutive ones in the output sequence. An all-ones sequence of fixed length is appended to serve as a sync marker when the codewords are concatenated. The bit-stuffing technique ensures that the sync markers do not occur anywhere except at the boundaries between the codewords. Expressions for the optimal choice of the marker length and the block length are derived. The performance of the proposed code is determined in terms of redundancy and error resilience. An upper bound on the average error rate is derived and its tightness is confirmed with computer simulations. The proposed code shows to significantly suppress the error rate at the expense of a minimum increase in redundancy.

An anti-dictionary is in particular useful for data compression, and it consists of minimal forbidden words for a given string. We derive the average length Mnof minimal forbidden words in strings of length n under a stationary ergodic source with entropy H which takes values on a finite alphabet. For the string length n, we prove, log n/Mn= H, in probability, as n rarr infin. We use the Wyner-Ziv result, with respect to connection between entropy and recurrence-time for ergodic processes, to prove the theorem. Its validity is shown by simulation results on a memoryless binary information source.

In this paper we propose an algorithm to adjust the transmission bit-rate of variable-bit-rate (VBR) MPEG video data by using a combination of transcoding and bit-rate smoothing algorithm. The algorithm works by smoothing out the bit-rate of high variance MPEG video data and when necessary transcodes some video frames in order to keep the video transmission bit-rate below a determined threshold value. This technique is useful for a live video streaming application in which an originally high-quality VBR video data for broadband users must also be delivered to other type of users where their allowed bit-rate and its variation is tightly constrained, such as mobile phone users, without sacrificing the quality of video images too much. Quality degradation caused by transcoding can be reduced by the smoothing process, which will make the number of frames required to be transcoded can be much lower than doing transcoding solely. Depending on the threshold value, our experiment results show that the number frames needed to be transcoded can be reduced significantly.

Integer codes, defined over integer rings, allow the correction of single cross errors with distance 1 in a signal point constellation on a two-dimensional lattice. Several construction methods support the construction of integer codes that give constellations that have a variety of shapes. In this paper, we characterize all constellations that can be obtained from a particular integer code. In particular, we determine those that minimize the average symbol energy. In addition, we evaluate the symbol error probability when using an integer code for coded QAM constellations.

This paper proposes an on-line data compression based on antidictionaries with linear time. The proposed algorithm works using only suffix trees without constructing of antidictionaries, and we prove that the time complexity of this algorithm is linear with respect to the string length. Furthermore, the proposed algorithm produces the tree model based on antidictionaries. This tree model gives an efficient probabilistic model for entropy codings. Its effectiveness is demonstrated by simulation results.

We consider the class of integer codes that are capable of correcting single errors in a two-dimensional lattice (H. Morita et al., 2003). Integer codes, defined over integer rings, allow the correction of single errors with distance 1. In this paper, we extend our previous results (H. Morita et al., 2003). We will detail the derivation of an upper bound on the code size and give constructions that attain this bound. Next, several coding algorithms are presented that efficiently transform binary information into a sequence of symbols that are associated with signal points in a two-dimensional lattice. The proposed decoding algorithms can correct any single error with distance 1 in the given signal point constellation and restore the binary information. We will present a systematic technique to design signal point constellations that support the constructed integer codes and that are optimal in terms of the total Mannheim and Euclidean distance

An antidictionary of a binary string is a set of words of minimal length that never appear in this string. Antidictionaries are in particular useful for source coding. We present a fast and memory-efficient algorithm to construct an antidictionary for a binary string using a suffix tree. It is proved that the complexity of this algorithm is linear in space and time, and its effectiveness is demonstrated by simulation results

A new class of DC-free codes of odd length is presented. The new codes, related to polarity-switch (PS) codes, make use of a redefinition of the running digital sum. The spectral efficiency of the new codes is determined, and it is shown that they provide better power suppression in the low-frequency region than classical PS codes

Coded modulation refers to the process of combined and jointly optimized channel coding and modulation scheme. In this paper, block coded modulation using integer codes and its performance is evaluated by deriving a formula of its bit error probability for AWGN channel. The probability of correct detection of the received signal is a square of the corresponding probability. The detector correctly demodulates the received signal with an average probability in uncoded and coded case respectively.

A new class of codes for frame synchronization is proposed. Commonly, the beginning of every fixed or variable-length frame is identified by a given contiguous sequence called a prefix. To avoid the occurrence of the prefix elsewhere in the frame, a prefix synchronizable code (PS-code) is used. PS-codes have the property that the prefix does not occur in any codeword or in any concatenation of codewords in any position other than the first position. The new codes, termed partial-prefix synchronizable codes (PPS-codes), use a fixed sequence of symbols that is interspersed with symbols that carry information. The contiguous sequence from the first fixed symbol to the last fixed symbol is called a "partial-prefix." Consequently, not one but a set of possible prefixes is used, and none of these prefixes is allowed to occur at any other than the first position of a codeword. The cardinality of PPS-codes is determined, and coding algorithms are proposed which have a computational complexity proportional to the length of the codewords. It is demonstrated that in comparison with PS-codes, PPS-codes have similar coding and prefix detection complexity, but they have a larger code size and have better error control capabilities.

We consider a new class of information sources called word-valued sources in order to investigate coding algorithms based upon string parsing. A word-valued source is defined as a pair of an independent and identically distributed (i.i.d.) source with a countable alphabet and a function that maps each symbol into a finite sequence over a finite alphabet. A word-valued source is a nonstationary process and has countable states. If the function of a word-valued source is prefix-free, the entropy rate is characterized with a simple expression and the AEP (asymptotic equipartition property) holds.

We present a systematic procedure for mapping data sequences into codewords of a prefix-synchronized code (PS-code), as well as for performing the inverse mapping. A PS-code, proposed by Gilbert (1960), belongs to a subclass of comma-free codes and is useful to recover word synchronization when errors have occurred in the stream of codewords. A PS-code is defined as a set of codewords with the property that each codeword has a known sequence as a prefix, followed by a coded data sequence in which this prefix is not allowed to occur. The largest PS-code among all PS-codes of the same code length is called a maximal prefix-synchronized code (MPS-code). We develop an encoding and decoding algorithm for Gilbert's MPS-code with a prefix of the form 11...10 and extend the algorithm to the class PS-codes of which the prefix is self-uncorrelated. The computational complexity of the entire mapping process is proportional to the length of the codewords.

The authors modify the algorithm of Z. Ziv and A. Lempel (1977), LZ77, restricting pointers to start only at the boundary of a previously parsed phrase in a window. Although the number of parsed phrases should increase more than those in LZ77, the number of bits needed to encoded pointers is considerably reduced since the number of possible positions to be encoded is much smaller. It is shown that, for any stationary finite state source, the modified LZ77 code is asymptotically optimal with the convergence rate O(log log M/log M), where M is the size of a sliding window.>

A common problem of Pattern projection methods to measure surfaces of 3-D objects is that an observed pattern possibly i ncludes disorders such as deficiency, d isplacement, and permutation of subpatterns. These disorders make it difficult to match observed patterns with its position on the projected one and cause wrong m easurements as a result. This paper proposes a new technique to correct pattern disorders by using a pattern made from an M-array which is a two-dimensional extension of a well-known M-sequence.

A new coding technique called SECT for digitized two-tone or black/white pictures which is particularly applicable to polygonal objects composed of horizontal, vertical, and diagonal lines such as logical circuit patterns, characteristic font patterns, and mechanical drawings is described. While many previously proposed coding techniques attempt to encode the positions of transitive elements in a picture by using codes such as Huffman codes or Wyle codes which are constructed on the basis of picture statistics, selective element coding technique (SECT) focuses its attention on reducing the number of transitive elements in each picture independently of the statistics of the picture ensemble. The relation of the number of selective elements and objects in the picture is discussed. Furthermore the decoding algorithm to reproduce a picture from selective elements and its decodability are described.