ScholarBank@NUShttps://scholarbank.nus.edu.sgThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Fri, 07 Oct 2022 16:10:51 GMT2022-10-07T16:10:51Z50231- The characterization of 2n-periodic binary sequences with fixed 1-error linear complexityhttps://scholarbank.nus.edu.sg/handle/10635/111649Title: The characterization of 2n-periodic binary sequences with fixed 1-error linear complexity
Authors: Fu, F.-W.; Niederreiter, H.; Su, M.
Abstract: The linear complexity of sequences is one of the important security measures for stream cipher systems. Recently, using fast algorithms for computing the linear complexity and the k-error linear complexity of 2 n-periodic binary sequences, Meidl determined the counting function and expected value for the 1-error linear complexity of 2n-periodic binary sequences. In this paper, we study the linear complexity and the 1-error linear complexity of 2n-periodic binary sequences. Some interesting properties of the linear complexity and the 1-error linear complexity of 2 n-periodic binary sequences are obtained. Using these properties, we characterize the 2n-periodic binary sequences with fixed 1-error linear complexity. Along the way, we obtain a new approach to derive the counting function for the 1-error linear complexity of 2n-periodic binary sequences. Finally, we give new fast algorithms for computing the 1-error linear complexity and locating the error positions for 2n-periodic binary sequences. © Springer-Verlag Berlin Heidelberg 2006.
Sun, 01 Jan 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1116492006-01-01T00:00:00Z
- A generalization of MDS codeshttps://scholarbank.nus.edu.sg/handle/10635/111517Title: A generalization of MDS codes
Authors: Luo, Y.; Fu, F.-W.; Mitrpant, C.; Vinck, A.J.H.
Abstract: The maximum distance separable (MDS) code was extended to a two-code formate, the code and a subcode. The pair was called a relative MDS pair if its inverse relative dimension/length profile (IRDLP) reached the generalized Singleton bound. The generalized Singleton bound on IRDLP was derived to maximize the equivocation. The properties and constructions of relative MDS pairs were also considered.
Thu, 01 Jan 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1115172004-01-01T00:00:00Z
- A new kind of geometric structures determining the chain good weight hierarchieshttps://scholarbank.nus.edu.sg/handle/10635/111313Title: A new kind of geometric structures determining the chain good weight hierarchies
Authors: Luo, Y.; Chen, W.; Fu, F.
Abstract: In this paper, by using a new kind of geometric structures, we present some sufficient conditions to determine the weight hierarchies of linear codes satisfying the chain condition. © 2002 Elsevier Science B.V. All rights reserved.
Tue, 01 Jan 2002 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1113132002-01-01T00:00:00Z
- On Constant-Composition Codes Over Z qhttps://scholarbank.nus.edu.sg/handle/10635/111448Title: On Constant-Composition Codes Over Z q
Authors: Luo, Y.; Fu, F.-W.; Vinck, A.J.H.; Chen, W.
Abstract: A constant-composition code is a special constant-weight code under the restriction that each symbol should appear a given number of times in each codeword. In this correspondence, we give a lower bound for the maximum size of the q-ary constant-composition codes with minimum distance at least 3. This bound is asymptotically optimal and generalizes the Graham-Sloane bound for binary constant-weight codes. In addition, three construction methods of constant-composition codes are presented, and a number of optimum constant-composition codes are obtained by using these constructions.
Sat, 01 Nov 2003 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1114482003-11-01T00:00:00Z
- On the constructions and nonlinearity of binary vector-output correlation-immune functionshttps://scholarbank.nus.edu.sg/handle/10635/111449Title: On the constructions and nonlinearity of binary vector-output correlation-immune functions
Authors: Chen, L.; Fu, F.-W.; Wei, V.K.-W.
Abstract: The binary vector-output correlation-immune functions are studied in this paper. Some important properties of vector-output correlation-immune functions are obtained. A number of methods for constructing new vector-output correlation-immune functions from old ones are discussed. The nonlinearity of the newly constructed vector-output correlation-immune functions is studied. For some cases we give the exact formulas for the nonlinearity of constructed vector-output correlation-immune functions. © 2003 Elsevier Inc. All rights reserved.
Thu, 01 Apr 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1114492004-04-01T00:00:00Z
- On the minimum pseudo-codewords of LDPC codeshttps://scholarbank.nus.edu.sg/handle/10635/111451Title: On the minimum pseudo-codewords of LDPC codes
Authors: Xia, S.-T.; Fu, F.-W.
Abstract: In this letter, we study the minimum pseudo-codewords of low-density parity-check (LDPC) codes under linear programming (LP) decoding. We show that a lower bound of Chaichanavong and Siegel on the pseudo-weight of a pseudo-codeword is tight if and only if this pseudo-codeword is a real multiple of a codeword. Using this result we further show that for some LDPC codes, e.g., Euclidean plane and projective plane LDPC codes, there are no other minimum pseudo-codewords except the real multiples of minimum codewords. © 2006 IEEE.
Mon, 01 May 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1114512006-05-01T00:00:00Z
- On the counting function of the lattice profile of periodic sequenceshttps://scholarbank.nus.edu.sg/handle/10635/111450Title: On the counting function of the lattice profile of periodic sequences
Authors: Fu, F.-W.; Niederreiter, H.
Abstract: The lattice profile analyzes the intrinsic structure of pseudorandom number sequences with applications in Monte Carlo methods and cryptology. In this paper, using the discrete Fourier transform for periodic sequences and the relation between the lattice profile and the linear complexity, we give general formulas for the expected value, variance, and counting function of the lattice profile of periodic sequences with fixed period. Moreover, we determine in a more explicit form the expected value, variance, and counting function of the lattice profile of periodic sequences for special values of the period. © 2006 Elsevier Inc. All rights reserved.
Wed, 01 Aug 2007 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1114502007-08-01T00:00:00Z
- On the undetected error probability for binary codeshttps://scholarbank.nus.edu.sg/handle/10635/111455Title: On the undetected error probability for binary codes
Authors: Fu, F.-W.; Kløve, T.; Wei, V.K.-W.
Abstract: In this paper, the undetected error probability for binary codes is studied. First complementary codes are studied. Next, a new proof of Abdel-Ghaffar's lower bound on the undetected error probability is presented and some generalizations are given. Further, upper and lower bounds on the undetected error probability for binary constant weight codes are given, and asymptotic versions are studied.
Sat, 01 Feb 2003 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1114552003-02-01T00:00:00Z
- Two constructions of permutation arrayshttps://scholarbank.nus.edu.sg/handle/10635/111663Title: Two constructions of permutation arrays
Authors: Fu, F.-W.; Kløve, T.
Abstract: In this correspondence, two new constructions of permutation arrays are given. A number of examples to illustrate the constructions are also provided.
Sat, 01 May 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1116632004-05-01T00:00:00Z
- On the variance of average distance of subsets in the Hamming spacehttps://scholarbank.nus.edu.sg/handle/10635/111456Title: On the variance of average distance of subsets in the Hamming space
Authors: Fu, F.-W.; Ling, S.; Xing, C.
Abstract: Let V be a finite set with q distinct elements. For a subset C of V n, denote var(C) the variance of the average Hamming distance of C. Let T(n, M; q) and R(n, M; q) denote the minimum and maximum variance of the average Hamming distance of subsets of Vn with cardinality M, respectively. In this paper, we study T(n, M; q) and R(n, M; q) for general q. Using methods from coding theory, we derive upper and lower bounds on var(C), which generalize and unify the bounds for the case q = 2. These bounds enable us to determine the exact value for T(n, M; q) and R(n, M; q) in several cases. © 2004 Elsevier B.V. All rights reserved.
Sun, 30 Jan 2005 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1114562005-01-30T00:00:00Z
- The expectation and variance of the joint linear complexity of random periodic multisequenceshttps://scholarbank.nus.edu.sg/handle/10635/111494Title: The expectation and variance of the joint linear complexity of random periodic multisequences
Authors: Fu, F.-W.; Niederreiter, H.; Su, M.
Abstract: The linear complexity of sequences is one of the important security measures for stream cipher systems. Recently, in the study of vectorized stream cipher systems, the joint linear complexity of multisequences has been investigated. By using the generalized discrete Fourier transform for multisequences, Meidl and Niederreiter determined the expectation of the joint linear complexity of random N-periodic multisequences explicitly. In this paper, we study the expectation and variance of the joint linear complexity of random periodic multisequences. Several new lower bounds on the expectation of the joint linear complexity of random periodic multisequences are given. These new lower bounds improve on the previously known lower bounds on the expectation of the joint linear complexity of random periodic multisequences. By further developing the method of Meidl and Niederreiter, we derive a general formula and a general upper bound for the variance of the joint linear complexity of random N-periodic multisequences. These results generalize the formula and upper bound of Dai and Yang for the variance of the linear complexity of random periodic sequences. Moreover, we determine the variance of the joint linear complexity of random periodic multisequences with certain periods. © 2005 Elsevier Inc. All rights reserved.
Thu, 01 Dec 2005 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1114942005-12-01T00:00:00Z
- The characterization of binary constant weight codes meeting the bound of Fu and Shenhttps://scholarbank.nus.edu.sg/handle/10635/111493Title: The characterization of binary constant weight codes meeting the bound of Fu and Shen
Authors: Fu, F.-W.; Xia, S.-T.
Abstract: Fu and Shen gave an upper bound on binary constant weight codes. In this paper, we present a new proof for the bound of Fu and Shen and characterize binary constant weight codes meeting this bound. It is shown that binary constant weight codes meet the bound of Fu and Shen if and only if they are generated from certain symmetric designs and quasi-symmetric designs in combinatorial design theory. In particular, it turns out that the existence of binary codes with even length meeting the Grey-Rankin bound is equivalent to the existence of certain binary constant weight codes meeting the bound of Fu and Shen. Furthermore, some examples are listed to illustrate these results. Finally, we obtain a new upper bound on binary constant weight codes which improves on the bound of Fu and Shen in certain case. © Springer Science+Business Media, LLC 2007.
Sun, 01 Apr 2007 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1114932007-04-01T00:00:00Z
- A lower bound on the probability of undetected error for binary constant weight codeshttps://scholarbank.nus.edu.sg/handle/10635/111522Title: A lower bound on the probability of undetected error for binary constant weight codes
Authors: Xia, S.-T.; Fu, F.-W.; Ling, S.
Abstract: In this paper, we study the probability of undetected error for binary constant weight codes (BCWCs). First, we derive a new lower bound on the probability of undetected error. Next, we show that this bound is tight if and only if the BCWCs are generated from certain t-designs. This means that such BCWCs are uniformly optimal for error detection. Thus, we prove a conjecture of Xia, Fu, Jiang and Ling. Furthermore, we determine the distance distributions of such BCWCs. Finally, we derive some bounds on the exponent of the probability of undetected error for BCWCs. These bounds enable us to extend the region in which the exponent of the probability of undetected error is exactly determined. © 2006 IEEE.
Sun, 01 Jan 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1115222006-01-01T00:00:00Z
- The probability of undetected error for binary constant-weight codeshttps://scholarbank.nus.edu.sg/handle/10635/111497Title: The probability of undetected error for binary constant-weight codes
Authors: Xia, S.-T.; Fu, F.-W.; Jiang, Y.; Ling, S.
Abstract: In this correspondence, we study the probability of undetected error for binary constant-weight codes. First, we derive a new formula on the probability of undetected error for binary constant-weight codes. Second, using this new formula and linear programming, we give two new lower bounds on the probability of undetected error for binary constant-weight codes. These two new lower bounds improve on previously known lower bounds in certain cases. Furthermore, we show that these two lower bounds are tight if and only if the binary constant-weight codes are generated from certain t-designs in combinatorial design theory. This means that these binary constant-weight codes generated from certain t-designs are uniformly optimal for error detection. Along the way, we determine the distance distributions of such binary constant-weight codes. Finally, several examples are given to illustrate the results obtained in this correspondence. © 2005 IEEE.
Thu, 01 Sep 2005 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1114972005-09-01T00:00:00Z
- A lower bound on the probability of undetected error for binary constant weight codeshttps://scholarbank.nus.edu.sg/handle/10635/111311Title: A lower bound on the probability of undetected error for binary constant weight codes
Authors: Xia, S.-T.; Fu, F.-W.; Ling, S.
Abstract: In this correspondence, we study the probability of undetected error for binary constant weight codes. First, we derive a new lower bound on the probability of undetected error for binary constant weight codes. Next, we show that this bound is tight if and only if the binary constant weight codes are generated from certain t-designs in combinatorial design theory. This means that these binary constant weight codes generated from certain t-designs are uniformly optimal for error detection. Along the way, we determine the distance distributions of such binary constant weight codes. In particular, it is shown that binary constant weight codes generated from Steiner systems are uniformly optimal for error detection. Thus, we prove a conjecture of Xia, Fu, Jiang, and Ling. Furthermore, the distance distribution of a binary constant weight code generated from a Steiner system is determined. Finally, we study the exponent of the probability of undetected error for binary constant weight codes. We derive some bounds on the exponent of the probability of undetected error for binary constant weight codes. These bounds enable us to extend the region in which the exponent of the probability of undetected error is exactly determined. © 2006 IEEE.
Fri, 01 Sep 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1113112006-09-01T00:00:00Z
- On the rate-distortion region for multiple descriptionshttps://scholarbank.nus.edu.sg/handle/10635/111452Title: On the rate-distortion region for multiple descriptions
Authors: Fu, F.-W.; Yeung, R.W.
Abstract: In this paper, we study the problem of source coding with multiple descriptions, which is described as follows. Let X be a discrete memoryless source. There are two encoders, Encoders 1 and 2, and three decoders, Decoders 0, 1, and 2. Encoders 1 and 2 describe the source X at respective rates R 1 and R 2. Decoder 1 receives the output of Encoder 1 only, and it can recover X with distortion D 1. Decoder 2 receives the output of Encoder 2 only, and it can recover X with distortion D 2. Decoder 0 receives the outputs of both Encoders 1 and 2, and it can recover X with distortion D 0. We show that if Decoder 2 (or Decoder 1) is required to recover a function of the source X perfectly in the usual Shannon sense, the El Gamal-Cover inner bound on the rate distortion region is tight. This finding subsumes the Rimoldi rate-distortion region for successive refinement of information, the Kaspi rate-distortion function when side information may be present at the decoder, and the El Gamal-Cover achievable rate region for multiple descriptions with deterministic distortion measures. We have also obtained a new outer bound on the rate-distortion region which enhances the outer bound due to Witsenhausen and Wyner. This new outer bound implies some interesting facts regarding the achievable rate-distortion vectors. Finally, we pose a multilevel diversity source coding problem for further study.
Mon, 01 Jul 2002 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1114522002-07-01T00:00:00Z
- On the reliability-order-based decoding algorithms for binary linear block codeshttps://scholarbank.nus.edu.sg/handle/10635/111453Title: On the reliability-order-based decoding algorithms for binary linear block codes
Authors: Tang, Y.; Ling, S.; Fu, F.-W.
Abstract: In this correspondence, we consider the decoding of binary block codes over the additive white Gaussian noise (AWGN) channel with binary phase-shift keying (BPSK) signaling. By a reliability-order-based decoding algorithm (ROBDA), we mean a soft-decision decoding algorithm which decodes to the best (most likely) codeword of the form that is the sum of the hard-decision tuple and an error pattern in a set determined only by the order of the reliabilities of the hard decisions. Examples of ROBDAs include many well-known decoding algorithms, such as the generalized-minimum-distance (GMD) decoding algorithm, Chase decoding algorithms, and the reliability-based decoding algorithms proposed by Fossorier and Lin. It is known that the squared error-correction-radii of ROBDAs can be computed from the minimal squared Euclidean distances (MSEDs) between the all-one sequence and the polyhedra corresponding to the error patterns. For the computation of such MSEDs, we give a new method which is more compact than the one proposed by Fossorier and Lin. These results are further used to show that any bounded-distance ROBDA is asymptotically optimal: The ratio between the probability of decoding error of a bounded-distance ROBDA and that of the maximum-likelihood (ML) decoding approaches 1 when the signal-to-noise ratio (SNR) approaches infinity, provided that the minimum Hamming distance of the code is greater than 2. © 2006 IEEE.
Sun, 01 Jan 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1114532006-01-01T00:00:00Z
- On Constant-Composition Codes Over Z qhttps://scholarbank.nus.edu.sg/handle/10635/114907Title: On Constant-Composition Codes Over Z q
Authors: Luo, Y.; Fu, F.-W.; Vinck, A.J.H.; Chen, W.
Abstract: A constant-composition code is a special constant-weight code under the restriction that each symbol should appear a given number of times in each codeword. In this correspondence, we give a lower bound for the maximum size of the q-ary constant-composition codes with minimum distance at least 3. This bound is asymptotically optimal and generalizes the Graham-Sloane bound for binary constant-weight codes. In addition, three construction methods of constant-composition codes are presented, and a number of optimum constant-composition codes are obtained by using these constructions.
Sat, 01 Nov 2003 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1149072003-11-01T00:00:00Z
- On equidistant constant weight codeshttps://scholarbank.nus.edu.sg/handle/10635/111618Title: On equidistant constant weight codes
Authors: Fu, F.-W.; Kloøve, T.; Luo, Y.; Wei, K.V.
Abstract: Equidistant constant weight codes are studied in this paper. The dual distance distribution of equidistant constant weight codes is investigated and used to obtain upper bounds on the size of such codes as well as equidistant codes in general. © 2003 Elsevier Science B.V. All rights reserved.
Thu, 15 May 2003 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1116182003-05-15T00:00:00Z
- New Lower Bounds and Constructions for Binary Codes Correcting Asymmetric Errorshttps://scholarbank.nus.edu.sg/handle/10635/111445Title: New Lower Bounds and Constructions for Binary Codes Correcting Asymmetric Errors
Authors: Fu, F.-W.; Ling, S.; Xing, C.
Abstract: In this correspondence, we study binary asymmetric error-correcting codes. A general construction for binary asymmetric error-correcting codes is presented. We show that some previously known lower bounds for binary asymmetric error-correcting codes can be obtained from this general construction. Furthermore, some new lower bounds for binary asymmetric error-correcting codes are obtained from this general construction. These new lower bounds improve the existing ones.
Mon, 01 Dec 2003 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1114452003-12-01T00:00:00Z
- On the stopping distance of finite geometry LDPC codeshttps://scholarbank.nus.edu.sg/handle/10635/111454Title: On the stopping distance of finite geometry LDPC codes
Authors: Xia, S.-T.; Fu, F.-W.
Abstract: In this letter, the stopping sets and stopping distance of finite geometry LDPC (FG-LDPC) codes are studied. It is known that FG-LDPC codes are majority-logic decodable and a lower bound on the minimum distance can be thus obtained. It is shown in this letter that this lower bound on the minimum distance of FG-LDPC codes is also a lower bound on the stopping distance of FG-LDPC codes, which implies that FG-LDPC codes have considerably large stopping distance. This may explain in one respect why some FG-LDPC codes perform well with iterative decoding in spite of having many cycles of length 4 in their Tanner graphs. © 2006 IEEE.
Mon, 01 May 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1114542006-05-01T00:00:00Z
- On the capacity of write-unidirectional memories with nonperiodic codeshttps://scholarbank.nus.edu.sg/handle/10635/111662Title: On the capacity of write-unidirectional memories with nonperiodic codes
Authors: Fu, F.-W.; Vinck, A.J.H.; Wei, V.K.; Yeung, R.W.
Abstract: Write-unidirectional memories (WUMs) were introduced by Willems, Vinck, and Borden as an information-theoretic model for storing and updating information on a rewritable medium with the writing constraints: During the odd (resp., even) cycles of updating information, the encoder can only write 1 's (resp., 0's) in selected bit positions of WUMs, and not change the contents of other positions. In this correspondence, motivated by the research works of Wolf, Wyner, Ziv, and Korner on write-once memories (WOMs), we study the problem of how to reuse a WUM for fixed T successive cycles with nonperiodic codes (i.e., all coding strategies are permitted for every cycle). For the situation where the encoder knows and the decoder does not know the previous content of the memory, we determine the zero-error capacity region, the average capacity, and the maximum total number of information bits stored in the WUM for fixed T successive cycles. Motivated by the research works of Heegard on WOMs with symmetric input noise, we introduce two models of WUMs with symmetric or asymmetric input noise. By using ε-error as performance criterion, we extend the above results for WUMs to the two models of WUMs with symmetric or asymmetric input noise.
Thu, 01 Apr 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1116622004-04-01T00:00:00Z
- Codes for key generation in quantum cryptographyhttps://scholarbank.nus.edu.sg/handle/10635/111345Title: Codes for key generation in quantum cryptography
Authors: Englert, B.-G.; Fu, F.-W.; Niederreiter, H.; Xing, C.
Abstract: As an alternative to the usual key generation by two-way communication in schemes for quantum cryptography, we consider codes for key generation by one-way communication. We study codes that could be applied to the raw key sequences that are ideally obtained in recently proposed scenarios for quantum key distribution, which can be regarded as communication through symmetric four-letter channels. © World Scientific Publishing Company.
Tue, 01 Nov 2005 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1113452005-11-01T00:00:00Z