39

논문 09-34-07-01 한국통신학회논문지 '09-07 Vol. 34 No. 7 행벡터집합이벡터공간을이루는하다마드행렬의동치관계 진석용 *, 김정헌 **, 박기현 *, 종신회원송홍엽 * Equivalence of Hadamard Matrices Whose Rows Form a Vector Space Seok-Yong Jin*, Jeong-Heon Kim**, Ki-Hyeon Park* Hong-Yeop Song* Lifelong Member Regular Members 요 약 본논문에서는행벡터의집합이이진벡터합연산에관해닫혀있는모든하다마드 (Hadamard) 행렬들은서로동치 (equivalent) 임을증명한다. 이를이용하면, 최대길이수열로부터생성된순회 (cyclic) 하다마드행렬과크로네커 (Kronecker) 곱에의해생성된월쉬- 하다마드 (Walsh-Hadamard) 행렬이동치임을간단히보일수있다. Key Words : Hadamard matrices, Hadamard equivalence, Walsh-Hadamard matrices, Kronecker product, m-sequences ABSTRACT In this paper, we show that any two Hadamard matrices of the same size are equivalent if they have the property that the rows of each Hadamard matrix are closed under binary vector addition. One of direct consequences of this result is that the equivalence between cyclic Hadamard matrices constructed by maximal length sequences and Walsh-Hadamard matrix of the same size generated by Kronecker product can be established. Ⅰ. 서론원소가 -1과 +1로이루어진 정방행렬 이다음성질 (1) 을만족하면 을 차하다마드 (Hadamard) 행렬이라한다. 여기서 은 차단위행렬이다. 하다마드행렬은오류정정부호를비롯한통신용신호설계분야에서영상신호처리분야까지광범위하 게응용된다 [1]-[4]. 하다마드행렬이 1960년대미국 JPL(Jet Propulsion Laboratory) 의 M. Hall, Jr., L. Baumert, 그리고 S. Golomb 등에의해 Mariner, Voyager 우주탐사선의이미지전송에채용된이래로 90년대 Gallileo 탐사선에서도사용되었음은잘알려져있다 [5]. 하다마드행렬 이존재하면 은 1, 2, 혹은 4 의배수이며, 의임의의행혹은열에 -1을곱하거나임의의두행혹은열을맞바꾸어도 (1) 을만족함을쉽게알수있다. 두하다마드행렬 와 에관하여 에행렬연산 a) 와연산 b) 를반복 본연구는한국과학재단특정기초연구 (R01-2008-000-11104-0) 지원으로수행되었습니다. * 연세대학교전기전자공학과부호및암호연구실 ({sy.jin, kh.park, hysong}@yonsei.ac.kr) ** 삼성전자 (jeongheon.kim@samsung.com) 논문번호 :KICS2009-05-186, 접수일자 :2009 년 5 월 5 일, 최종논문접수일자 :2009 년 7 월 1 일 635

한국통신학회논문지 '09-07 Vol. 34 No. 7 적용해서 을얻을수있으면 와 은동치 (equivalent) 인하다마드행렬이라고정의한다. 연산 a) 임의의두행 ( 혹은열 ) 을서로맞바꾼다. 연산 b) 임의의행 ( 혹은열 ) 에 -1을곱한다. 하다마드행렬의생성및분류그리고그응용분야에관한다양한연구주제중, 하다마드행렬의동치관계에관한연구는오랫동안주목을받고있는중요한연구주제이다. 서로다른 (inequivlanet) 차하다마드행렬의개수를구하는문제는매우어려운문제로알려져있다 [6],[7]. 현재까지는그크기 에대해서만서로다른 (inequivalent) 하다마드행렬의개수가완전히알려져있을뿐이다. 특히 1960년대에 16차하다마드행렬이완전히분류된이후 1990년대초반에이르러서야 28차하다마드행렬의분류작업이마무리되었으며, 이에관한연구는현재까지도계속되고있다 [6]-[8]. 본논문에서는하다마드행렬의동치관계에관한다음성질을증명한다. 즉, 행벡터 (row vector) 집합이이진벡터합 (vector addition) 연산에관해닫혀있어그자체로벡터공간을이루는 차하다마드행렬들은모두동치임을보인다. 이는특정생성방법에구애받지않고하다마드행렬의동치관계를확립하는데중요하게사용될수있다. 논문의구성은다음과같다. 제 Ⅱ절에서는본논문의주된결과를증명한다. 제 Ⅲ절에서는제 Ⅱ 절의결과를이용한하나의이론적응용으로서, 월쉬-하다마드 (Walsh-Hadamard) 행렬과최대길이수열 (m-sequences) 을이용하여생성한순회 (cyclic) 하다마드행렬의동치관계확립및기존방법과의차별성을소개한다. 마지막으로제 Ⅳ절에서는본논문의결과를요약한다. [8, prop. 1.49] 표 1. 비동치 (inequivalent) 하다마드행렬의개수 n 4 8 12 16 20 24 28 32 36 # 1 1 1 5 3 60 487 >3.6 10 6 >15 10 6 Ⅱ. 주된결과 : 벡터합연산에관해닫혀있는행벡터들로이루어진하다마드행렬의동치관계 지금부터는하다마드행렬을지칭할때, 편의상원소 -1을 로, +1을 으로변경한행렬을뜻하기로하고, 을 차원이진벡터공간이라하자. 즉,. 만약 차하다마드행렬 의모든행벡터들로이루어진집합 가벡터합에관해닫혀있으면, 자신이벡터공간이다 [9]. 를 의 차원부분공간 (subspace) 이라하면, 는길이가 인영벡터 (zero vector) 를포함한 개의벡터를원소로갖는다. 정리 1 행벡터집합이벡터합에관해닫혀있는모든 차하다마드행렬은서로동치이다. 증명 와 을주어진조건을만족하는임의의두하다마드행렬이라하자. 편의상 이라하면, 와 공히 의 차원부분공간이다. 먼저, 의기저 (basis) 를 이라하고, 이를 (2) 와같이행렬형태로표시한다. (2) 이때, 의모든열 (column) 은서로다르다. 왜냐하면 에동일한열이있다면 에도동일한열이있어야하고, 이는하다마드행렬의정의상불가능하기때문이다. 따라서행렬 는정확히 개의길이 인이진열벡터 (column vector) 로구성된다. 마찬가지로 의기저를 (2) 와같은형태로적고이를 이라하면행렬 역시정확히 개의길이 인이진열벡터로구성된다. 그러므로 의열벡터의순서를재배치하여 과일치시킬수있다. 즉 의열벡터위치를치환하는 치환행렬 (permutation matrix) 가존재해서다음을만족한다. 이는 과 가동일한기저에의한펼침 (span) 공간임을뜻하므로 과 는집합으로서동일하다. 즉, 과 는동일한행벡터들로이루어진다. 따라서 와 은동치인하다마드행렬이다. 예 1 아래에표시된두개의 8 차하다마드행렬 와 을고려하자. 636

논문 / 행벡터집합이벡터공간을이루는하다마드행렬의동치관계 환 (circulant) 행렬이면 를순회 (cyclic) 하다마 드행렬이라한다. 그정의에의해, 순회하다마드 행렬은최적자기상관특성을갖는수열 [2],[10],[11], 즉, 모든시간지연에대한주기적자기상관 (periodic auto-correlation) 값이 -1인이진수열로부터생성된 다. 최적자기상관특성을갖는수열중가장널리 활용되는최대길이수열은여러가지의사잡음 의행벡터집합 와 의행벡터집합 (PN: Pseudo-Noise) 특성을지니며, 특별히 cycle- 모두벡터합에관해닫혀있으므로그자신 and-add 성질 [2],[10],[11] 을가진다. 그러므로최대길이이각각 3차원벡터공간이다. 각각의기저 와수열을이용하여생성한순회하다마드행렬의행 를아래와같이선택하자. 벡터집합역시벡터합에관해닫혀있다., 따라서정리 1에의해, 차월쉬 -하다마드행렬 과주기 인최대길이수열로부터생성된 차순회하다마드행렬은서로동치인하다마드행이때 렬이다. 예 1의 는 인치환행렬 를쉽게찾을수 차월쉬 -하다마드행렬이고있고 은주기가 7인최대길이수열 로부터이므로 와 은서로동치생성된순회하다마드행렬이다. 인하다마드행렬이다. 논의를최대길이수열을이용한순회하다마드행렬과월쉬-하다마드행렬에국한했을때, 두하다 Ⅲ. 주결과의응용예 : 월쉬- 하다마드행렬과마드행렬의동치관계는각각의행렬인수분해특성최대길이수열에의한순회하다마드행렬을이용하여보일수도있다 [12],[Ch.18]. 월쉬- 하다마드월쉬- 하다마드행렬과순회하다마드행렬은가행렬 은 행렬 에관해 와장널리활용되는두종류의하다마드행렬로서, 오같은형태로인수분해되며이때행렬 는모든류정정부호로서의직교부호와밀접한관련이있으 개의서로다른이진 m-tuple을그행으로갖는며영상신호처리를위한월쉬 -하다마드변환 (Wash- 다 [13]. 최대길이수열에의한순회하다마드행렬 Hadamard transform) 등에응용된다 [1]-[5]. 역시 ( 와같은크기의 ) 행렬 에관해 형먼저, 월쉬-하다마드행렬은 (3) 과같이연속된태로인수분해되며, 이때인수행렬 가최대계크로네커곱 (Kronecker product) 에의해재귀적으수 (rank) 값을가져야함은 Lempel의이진대칭행로생성된 차정방행렬이다. 렬의인수분해구조에관한결과 [14] 로부터알수있다. 반면본논문의정리 1은그대상을특정생성 방법에의한하다마드행렬로한정하지않는다. 또 (3) 한그증명과정에서드러나듯이, 임의의하다마드 행렬의행벡터집합이벡터부공간을이룰때그기저를행렬형태로표시하면최대계수 (full rank) 수학적귀납법을이용하여월쉬- 하다마드행렬의를가져야만한다는관찰에서비롯되었다. 이사실행벡터집합이벡터합에관해닫혀있음을쉽게보은, 최대길이수열에의해생성된순회하다마드행일수있다. 렬이나월쉬 -하다마드행렬등의공통적성질을추이번에는최대길이수열로부터생성된순회하다출한것으로서두하다마드행렬공히앞단락에서마드행렬을고려한다. 제 I절의연산 b) 에의해임설명한형태로인수분해되는근거를제공한다. 의의하다마드행렬의첫번째행과첫번째열의모든원소를 +1로정규화 (normalize) 할수있다. Ⅳ. 결론정규화된 차하다마드행렬 의첫번째행과첫번째열을제외한 ( ) 차정방행렬 가순본논문에서는행벡터집합이벡터합연산에관 637

한국통신학회논문지 '09-07 Vol. 34 No. 7 해닫혀있는모든 차하다마드행렬은서로동치임을보였다. 이결과는생성방법이상이한하다마드행렬의연관성규명및빠른하다마드변환 (fast Hadamard transform) 구현에응용될수있다. 참고문헌 [1] S. S. Agaian, Hadamard Matrices and Their Applications, Lecture Notes in Mathematics 1168, Springer-Verlag, 1985. [2] S. W. Golomb and G. Gong, Signal Design for Good Correlation, Cambridge University Press, 2005. [3] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977, Tenth impression, 1998. [4] H.-Y. Song and S. W. Golomb, Some new constructions for simplex codes, IEEE Transactions on Information Theory, 40:(2), pp.504-507, March, 1994. [5] J. Seberry and M. Yamada, Hadamard matrices, sequences, and block designs, in Contemporary Design Theory, edited by J. H. Dinitz and D. R. Stinson, John Wiley & Sons, pp.431-560, 1992. [6] N. J. A. Sloane and S. Plouffee, The Encyclopedia of Integer Sequences, Academic Press, 1995. See also: N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://www. research.att.com/~njas/sequences/a007299. [7] N. J. A. Sloane, My favorite integer sequences, in Sequences and Their Applications, edited by C. Ding, T. Helleseth and H. Niederreiter, Springer, 1999, pp.103-130. See also the extended version: http://www.research.att.com/~njas/doc/sg. pdf [8] R. Craigen and H. Kharaghani, Hadamard matrices and Hadamard designs, in Handbook of Combinatorial Designs, 2nd Ed., edited by C. J. Colbourn and J. H. Dinitz, Chapman & Hall/CRC, 2007, pp.273-280. [9] S. Lang, Linear Algebra, Third Edition, Springer, 1987. [10] S. W. Golomb, Shift Register Sequences, Revised Edition, Aegean Park Press, 1982, originally published by Hoden-Day in 1967. [11] H.-Y. Song, Feedback shift register sequences, in Wiley Encyclopedia of Telecommunications, edited by J. G. Proakis, John Wiley & Sons, pp.789-802, 2003. [12] R. K. Yarlagadda and J. E. Hershey, Hadamard Matrix Analysis and Synthesis, Kluwer Academic Publishers, 1997. [13] K. W. Henderson, Comment on Computations of the fast Walsh-Fourier transform, IEEE Transactions on Computers, 19:(9), pp.850-851, September, 1970. [14] A. Lempel, Matrix factorization over GF(2) and trace-orthogonal bases of GF(2n), SIAM Journal of Computation, 4:(2), pp.175-186, June, 1975. 진석용 (Seok-Yong Jin) 2001년 8월연세대학교전기전자공학과졸업 2003년 8월연세대학교전기전자공학과석사 2003년 9월 ~ 현재연세대학교전기전자공학과박사과정 < 관심분야 > PN Sequences, Error- Correcting Codes, Spread Spectrum Communications, Block/Stream Cipher Systems 김정헌 (Jeong-Heon Kim) 1996년 2월연세대학교전자공학과졸업 1998년 2월연세대학교전자공학과석사 2002년 2월연세대학교전기전자공학과박사 2002년 3월 ~ 현재삼성전자책임연구원 < 관심분야 > Mobile WiMax(WiBro), Error Correcting Codes, PN Sequences, CDMA 638

논문 / 행벡터집합이벡터공간을이루는하다마드행렬의동치관계 박기현 (Ki-Hyeon Park) 2007년 2월연세대학교전기전자공학과졸업 2009년 2월연세대학교전기전자공학과 ( 석사 ) 2009년 3월 ~ 현재연세대학교전기전자공학과박사과정 < 관심분야 > PN Sequences, Cryptography, Error-Correcting Codes 송홍엽 (Hong-Yeop Song) 종신회원 1984년 2월연세대학교전자공학과졸업 1986년 5월 USC(University of Southern California, USA) 대학원전자공학과 ( 공학석사 ) 1991년 12월 USC 대학원전자공학과 ( 공학박사 ) 1992년 1월 ~1994년 4월 USC Communication Science Institute, 박사후연구원 (Post-Doc) 1994년 5월 ~1996년 8월 Qualcomm Inc., San Diego, USA, 선임연구원 1995년 9월 ~1998년 2월연세대학교전자공학과조교수 1998년 3월 ~2003년 2월연세대학교전기전자공학과부교수 2002년 3월 ~2003년 2월 University of Waterloo, Canada, 방문연구교수 2003년 3월 ~ 현재연세대학교전기전자공학과교수 < 관심분야 > PN Sequences, Error Correcting Codes, Spread Spectrum Communication Systems, Steam Cipher Systems 639