Maximum Order Complexity for the Minimum Changes of an M-Sequence

• UEHARA Satoshi

  the Faculty of Computer Science and Systems Engineering, Kyushu Institute of Technology

• MORIUCHI Tsutomu

  the Department of Information and Electronics Engineering, Yatsushiro National College of Technology

• IMAMURA Kyoki

  the Faculty of Computer Science and Systems Engineering, Kyushu Institute of Technology

抄録

The maximum order complexity (MOC) of a sequence is a very natural generalization of the well-known linear complexity (LC) by allowing nonlinear feedback functions for the feedback shift register which generates a given sequence. It is expected that MOC is effective to reduce such an instability of LC as an extreme increase caused by the minimum changes of a periodic sequence, i. e., one-symbol substitution, one-symbol insertion or one-symbol deletion per each period. In this paper we well give the bounds (lower and upper bounds) of MOC for the minimum changes of an m-sequence over GF (q) with period q^n-1, which shows that MOC is much more natural than LC as a measure for the randomness of sequences in this case.

収録刊行物

• IEICE transactions on fundamentals of electronics, communications and computer sciences

  IEICE transactions on fundamentals of electronics, communications and computer sciences 81 (11), 2407-2411, 1998-11-25

  一般社団法人電子情報通信学会

キーワード

• maximum order complexity (MOC)
• instability of the linear complexity
• m-sequence
• bounds of MOC
• one-symbol substitution
• one-symbol insertion
• one-symbol deletion

詳細情報

• CRID: 1573950402231892736
• NII論文ID: 110003216419
• NII書誌ID: AA10826239
• ISSN: 09168508
• 本文言語コード: en
• データソース種別:
  • CiNii Articles