教えて!goo限定 1000名様に電子コミック1000円分が当たる!!

9段M系列の生成多項式となる原始多項式の求め方を教えてください。

今のところx^9+x^5+1やx^9+x^4+1が原始多項式であることがネットなどを調べていてわかりましたが、求め方はわかりません。
また、上記の2式が原始多項式であるかどうか判別するようなこともできるのでしょうか?

数学に関しては素人なので"何を勉強すればわかるか"だけでも教えていただけると助かります。

よろしくお願いします。

このQ&Aに関連する最新のQ&A

A 回答 (9件)

ついでに


x^kがどうなるかを示します。
右辺は位数2の素数体上多項式であって係数の並びで表現しています。

<?php
$N=9;
$p=32+1;
$c=pow(2,$N);
$f=$c^$p;
$a=1;
for($i=0;$i<$c;$i++)
{
$s=sprintf("x^(%03d) = %010b",$i,$a);
$color=($a==1)?"red":"blue";
print<<<EOL
<div style="color:{$color}">{$s}</div>
EOL;
$a<<=1;
if(($a & $c)==$c)$a^=$f;
}
?>

結果:
x^(000) = 0000000001
x^(001) = 0000000010
x^(002) = 0000000100
x^(003) = 0000001000
x^(004) = 0000010000
x^(005) = 0000100000
x^(006) = 0001000000
x^(007) = 0010000000
x^(008) = 0100000000
x^(009) = 0000100001
x^(010) = 0001000010
x^(011) = 0010000100
x^(012) = 0100001000
x^(013) = 0000110001
x^(014) = 0001100010
x^(015) = 0011000100
x^(016) = 0110001000
x^(017) = 0100110001
x^(018) = 0001000011
x^(019) = 0010000110
x^(020) = 0100001100
x^(021) = 0000111001
x^(022) = 0001110010
x^(023) = 0011100100
x^(024) = 0111001000
x^(025) = 0110110001
x^(026) = 0101000011
x^(027) = 0010100111
x^(028) = 0101001110
x^(029) = 0010111101
x^(030) = 0101111010
x^(031) = 0011010101
x^(032) = 0110101010
x^(033) = 0101110101
x^(034) = 0011001011
x^(035) = 0110010110
x^(036) = 0100001101
x^(037) = 0000111011
x^(038) = 0001110110
x^(039) = 0011101100
x^(040) = 0111011000
x^(041) = 0110010001
x^(042) = 0100000011
x^(043) = 0000100111
x^(044) = 0001001110
x^(045) = 0010011100
x^(046) = 0100111000
x^(047) = 0001010001
x^(048) = 0010100010
x^(049) = 0101000100
x^(050) = 0010101001
x^(051) = 0101010010
x^(052) = 0010000101
x^(053) = 0100001010
x^(054) = 0000110101
x^(055) = 0001101010
x^(056) = 0011010100
x^(057) = 0110101000
x^(058) = 0101110001
x^(059) = 0011000011
x^(060) = 0110000110
x^(061) = 0100101101
x^(062) = 0001111011
x^(063) = 0011110110
x^(064) = 0111101100
x^(065) = 0111111001
x^(066) = 0111010011
x^(067) = 0110000111
x^(068) = 0100101111
x^(069) = 0001111111
x^(070) = 0011111110
x^(071) = 0111111100
x^(072) = 0111011001
x^(073) = 0110010011
x^(074) = 0100000111
x^(075) = 0000101111
x^(076) = 0001011110
x^(077) = 0010111100
x^(078) = 0101111000
x^(079) = 0011010001
x^(080) = 0110100010
x^(081) = 0101100101
x^(082) = 0011101011
x^(083) = 0111010110
x^(084) = 0110001101
x^(085) = 0100111011
x^(086) = 0001010111
x^(087) = 0010101110
x^(088) = 0101011100
x^(089) = 0010011001
x^(090) = 0100110010
x^(091) = 0001000101
x^(092) = 0010001010
x^(093) = 0100010100
x^(094) = 0000001001
x^(095) = 0000010010
x^(096) = 0000100100
x^(097) = 0001001000
x^(098) = 0010010000
x^(099) = 0100100000
x^(100) = 0001100001
x^(101) = 0011000010
x^(102) = 0110000100
x^(103) = 0100101001
x^(104) = 0001110011
x^(105) = 0011100110
x^(106) = 0111001100
x^(107) = 0110111001
x^(108) = 0101010011
x^(109) = 0010000111
x^(110) = 0100001110
x^(111) = 0000111101
x^(112) = 0001111010
x^(113) = 0011110100
x^(114) = 0111101000
x^(115) = 0111110001
x^(116) = 0111000011
x^(117) = 0110100111
x^(118) = 0101101111
x^(119) = 0011111111
x^(120) = 0111111110
x^(121) = 0111011101
x^(122) = 0110011011
x^(123) = 0100010111
x^(124) = 0000001111
x^(125) = 0000011110
x^(126) = 0000111100
x^(127) = 0001111000
x^(128) = 0011110000
x^(129) = 0111100000
x^(130) = 0111100001
x^(131) = 0111100011
x^(132) = 0111100111
x^(133) = 0111101111
x^(134) = 0111111111
x^(135) = 0111011111
x^(136) = 0110011111
x^(137) = 0100011111
x^(138) = 0000011111
x^(139) = 0000111110
x^(140) = 0001111100
x^(141) = 0011111000
x^(142) = 0111110000
x^(143) = 0111000001
x^(144) = 0110100011
x^(145) = 0101100111
x^(146) = 0011101111
x^(147) = 0111011110
x^(148) = 0110011101
x^(149) = 0100011011
x^(150) = 0000010111
x^(151) = 0000101110
x^(152) = 0001011100
x^(153) = 0010111000
x^(154) = 0101110000
x^(155) = 0011000001
x^(156) = 0110000010
x^(157) = 0100100101
x^(158) = 0001101011
x^(159) = 0011010110
x^(160) = 0110101100
x^(161) = 0101111001
x^(162) = 0011010011
x^(163) = 0110100110
x^(164) = 0101101101
x^(165) = 0011111011
x^(166) = 0111110110
x^(167) = 0111001101
x^(168) = 0110111011
x^(169) = 0101010111
x^(170) = 0010001111
x^(171) = 0100011110
x^(172) = 0000011101
x^(173) = 0000111010
x^(174) = 0001110100
x^(175) = 0011101000
x^(176) = 0111010000
x^(177) = 0110000001
x^(178) = 0100100011
x^(179) = 0001100111
x^(180) = 0011001110
x^(181) = 0110011100
x^(182) = 0100011001
x^(183) = 0000010011
x^(184) = 0000100110
x^(185) = 0001001100
x^(186) = 0010011000
x^(187) = 0100110000
x^(188) = 0001000001
x^(189) = 0010000010
x^(190) = 0100000100
x^(191) = 0000101001
x^(192) = 0001010010
x^(193) = 0010100100
x^(194) = 0101001000
x^(195) = 0010110001
x^(196) = 0101100010
x^(197) = 0011100101
x^(198) = 0111001010
x^(199) = 0110110101
x^(200) = 0101001011
x^(201) = 0010110111
x^(202) = 0101101110
x^(203) = 0011111101
x^(204) = 0111111010
x^(205) = 0111010101
x^(206) = 0110001011
x^(207) = 0100110111
x^(208) = 0001001111
x^(209) = 0010011110
x^(210) = 0100111100
x^(211) = 0001011001
x^(212) = 0010110010
x^(213) = 0101100100
x^(214) = 0011101001
x^(215) = 0111010010
x^(216) = 0110000101
x^(217) = 0100101011
x^(218) = 0001110111
x^(219) = 0011101110
x^(220) = 0111011100
x^(221) = 0110011001
x^(222) = 0100010011
x^(223) = 0000000111
x^(224) = 0000001110
x^(225) = 0000011100
x^(226) = 0000111000
x^(227) = 0001110000
x^(228) = 0011100000
x^(229) = 0111000000
x^(230) = 0110100001
x^(231) = 0101100011
x^(232) = 0011100111
x^(233) = 0111001110
x^(234) = 0110111101
x^(235) = 0101011011
x^(236) = 0010010111
x^(237) = 0100101110
x^(238) = 0001111101
x^(239) = 0011111010
x^(240) = 0111110100
x^(241) = 0111001001
x^(242) = 0110110011
x^(243) = 0101000111
x^(244) = 0010101111
x^(245) = 0101011110
x^(246) = 0010011101
x^(247) = 0100111010
x^(248) = 0001010101
x^(249) = 0010101010
x^(250) = 0101010100
x^(251) = 0010001001
x^(252) = 0100010010
x^(253) = 0000000101
x^(254) = 0000001010
x^(255) = 0000010100
x^(256) = 0000101000
x^(257) = 0001010000
x^(258) = 0010100000
x^(259) = 0101000000
x^(260) = 0010100001
x^(261) = 0101000010
x^(262) = 0010100101
x^(263) = 0101001010
x^(264) = 0010110101
x^(265) = 0101101010
x^(266) = 0011110101
x^(267) = 0111101010
x^(268) = 0111110101
x^(269) = 0111001011
x^(270) = 0110110111
x^(271) = 0101001111
x^(272) = 0010111111
x^(273) = 0101111110
x^(274) = 0011011101
x^(275) = 0110111010
x^(276) = 0101010101
x^(277) = 0010001011
x^(278) = 0100010110
x^(279) = 0000001101
x^(280) = 0000011010
x^(281) = 0000110100
x^(282) = 0001101000
x^(283) = 0011010000
x^(284) = 0110100000
x^(285) = 0101100001
x^(286) = 0011100011
x^(287) = 0111000110
x^(288) = 0110101101
x^(289) = 0101111011
x^(290) = 0011010111
x^(291) = 0110101110
x^(292) = 0101111101
x^(293) = 0011011011
x^(294) = 0110110110
x^(295) = 0101001101
x^(296) = 0010111011
x^(297) = 0101110110
x^(298) = 0011001101
x^(299) = 0110011010
x^(300) = 0100010101
x^(301) = 0000001011
x^(302) = 0000010110
x^(303) = 0000101100
x^(304) = 0001011000
x^(305) = 0010110000
x^(306) = 0101100000
x^(307) = 0011100001
x^(308) = 0111000010
x^(309) = 0110100101
x^(310) = 0101101011
x^(311) = 0011110111
x^(312) = 0111101110
x^(313) = 0111111101
x^(314) = 0111011011
x^(315) = 0110010111
x^(316) = 0100001111
x^(317) = 0000111111
x^(318) = 0001111110
x^(319) = 0011111100
x^(320) = 0111111000
x^(321) = 0111010001
x^(322) = 0110000011
x^(323) = 0100100111
x^(324) = 0001101111
x^(325) = 0011011110
x^(326) = 0110111100
x^(327) = 0101011001
x^(328) = 0010010011
x^(329) = 0100100110
x^(330) = 0001101101
x^(331) = 0011011010
x^(332) = 0110110100
x^(333) = 0101001001
x^(334) = 0010110011
x^(335) = 0101100110
x^(336) = 0011101101
x^(337) = 0111011010
x^(338) = 0110010101
x^(339) = 0100001011
x^(340) = 0000110111
x^(341) = 0001101110
x^(342) = 0011011100
x^(343) = 0110111000
x^(344) = 0101010001
x^(345) = 0010000011
x^(346) = 0100000110
x^(347) = 0000101101
x^(348) = 0001011010
x^(349) = 0010110100
x^(350) = 0101101000
x^(351) = 0011110001
x^(352) = 0111100010
x^(353) = 0111100101
x^(354) = 0111101011
x^(355) = 0111110111
x^(356) = 0111001111
x^(357) = 0110111111
x^(358) = 0101011111
x^(359) = 0010011111
x^(360) = 0100111110
x^(361) = 0001011101
x^(362) = 0010111010
x^(363) = 0101110100
x^(364) = 0011001001
x^(365) = 0110010010
x^(366) = 0100000101
x^(367) = 0000101011
x^(368) = 0001010110
x^(369) = 0010101100
x^(370) = 0101011000
x^(371) = 0010010001
x^(372) = 0100100010
x^(373) = 0001100101
x^(374) = 0011001010
x^(375) = 0110010100
x^(376) = 0100001001
x^(377) = 0000110011
x^(378) = 0001100110
x^(379) = 0011001100
x^(380) = 0110011000
x^(381) = 0100010001
x^(382) = 0000000011
x^(383) = 0000000110
x^(384) = 0000001100
x^(385) = 0000011000
x^(386) = 0000110000
x^(387) = 0001100000
x^(388) = 0011000000
x^(389) = 0110000000
x^(390) = 0100100001
x^(391) = 0001100011
x^(392) = 0011000110
x^(393) = 0110001100
x^(394) = 0100111001
x^(395) = 0001010011
x^(396) = 0010100110
x^(397) = 0101001100
x^(398) = 0010111001
x^(399) = 0101110010
x^(400) = 0011000101
x^(401) = 0110001010
x^(402) = 0100110101
x^(403) = 0001001011
x^(404) = 0010010110
x^(405) = 0100101100
x^(406) = 0001111001
x^(407) = 0011110010
x^(408) = 0111100100
x^(409) = 0111101001
x^(410) = 0111110011
x^(411) = 0111000111
x^(412) = 0110101111
x^(413) = 0101111111
x^(414) = 0011011111
x^(415) = 0110111110
x^(416) = 0101011101
x^(417) = 0010011011
x^(418) = 0100110110
x^(419) = 0001001101
x^(420) = 0010011010
x^(421) = 0100110100
x^(422) = 0001001001
x^(423) = 0010010010
x^(424) = 0100100100
x^(425) = 0001101001
x^(426) = 0011010010
x^(427) = 0110100100
x^(428) = 0101101001
x^(429) = 0011110011
x^(430) = 0111100110
x^(431) = 0111101101
x^(432) = 0111111011
x^(433) = 0111010111
x^(434) = 0110001111
x^(435) = 0100111111
x^(436) = 0001011111
x^(437) = 0010111110
x^(438) = 0101111100
x^(439) = 0011011001
x^(440) = 0110110010
x^(441) = 0101000101
x^(442) = 0010101011
x^(443) = 0101010110
x^(444) = 0010001101
x^(445) = 0100011010
x^(446) = 0000010101
x^(447) = 0000101010
x^(448) = 0001010100
x^(449) = 0010101000
x^(450) = 0101010000
x^(451) = 0010000001
x^(452) = 0100000010
x^(453) = 0000100101
x^(454) = 0001001010
x^(455) = 0010010100
x^(456) = 0100101000
x^(457) = 0001110001
x^(458) = 0011100010
x^(459) = 0111000100
x^(460) = 0110101001
x^(461) = 0101110011
x^(462) = 0011000111
x^(463) = 0110001110
x^(464) = 0100111101
x^(465) = 0001011011
x^(466) = 0010110110
x^(467) = 0101101100
x^(468) = 0011111001
x^(469) = 0111110010
x^(470) = 0111000101
x^(471) = 0110101011
x^(472) = 0101110111
x^(473) = 0011001111
x^(474) = 0110011110
x^(475) = 0100011101
x^(476) = 0000011011
x^(477) = 0000110110
x^(478) = 0001101100
x^(479) = 0011011000
x^(480) = 0110110000
x^(481) = 0101000001
x^(482) = 0010100011
x^(483) = 0101000110
x^(484) = 0010101101
x^(485) = 0101011010
x^(486) = 0010010101
x^(487) = 0100101010
x^(488) = 0001110101
x^(489) = 0011101010
x^(490) = 0111010100
x^(491) = 0110001001
x^(492) = 0100110011
x^(493) = 0001000111
x^(494) = 0010001110
x^(495) = 0100011100
x^(496) = 0000011001
x^(497) = 0000110010
x^(498) = 0001100100
x^(499) = 0011001000
x^(500) = 0110010000
x^(501) = 0100000001
x^(502) = 0000100011
x^(503) = 0001000110
x^(504) = 0010001100
x^(505) = 0100011000
x^(506) = 0000010001
x^(507) = 0000100010
x^(508) = 0001000100
x^(509) = 0010001000
x^(510) = 0100010000
x^(511) = 0000000001
    • good
    • 0

N=8となっていましたがこちらの方で8次の原始多項式も見ていたので


結果とリストが食い違っていました。
結果はもちろん9次ですからN=9の結果です。
訂正します。

素数体2上の原始多項式を求めるプログラムをphpで作ってみたのですが
作る過程でプログラムを作るのに都合のよい条件は既に述べたものではなく次の方がいいという結論に達しました。

素数体2上のN次原始多項式f(x)の条件:
(1) x^(2^N-1)≡1 (mod f(x)) であること
(2) 0<n<2^N-1 なる整数nにおいて x^n≡1 (mod f(x)) でないこと

この条件だと既約多項式であることを要求する必要がないのでプログラミングが楽でした。
もちろん原始多項式は既約多項式であることに変わりはありません。
なお、既約多項式表と原始多項式表を同時に求める場合には先の条件の方が良いのです。

プログラムはPHPで作成しました。
なお、結果の原始多項式は左詰めで
高次から低次に向かって各次数の係数のみを並べて
1行1原始多項式で表示しました。

<?php
$N=9;
$c=pow(2,$N);
echo"{$N} 次原始多項式:<br/>";
for($p=1;$p<$c;$p++)
{
$f=$c^$p;
$a=1;
for($i=1;$i<$c;$i++)
{
$a<<=1;
if(($a & $c)==$c)$a^=$f;
if($a==1)break;
}
if($i==($c-1))
{
$s=sprintf("%b (%d xor %d)",$f,$c,$p);
echo"{$s}<br/>";
}
}
?>

結果:
9 次原始多項式:
1000010001 (512 xor 17)
1000011011 (512 xor 27)
1000100001 (512 xor 33)
1000101101 (512 xor 45)
1000110011 (512 xor 51)
1001011001 (512 xor 89)
1001011111 (512 xor 95)
1001101001 (512 xor 105)
1001101111 (512 xor 111)
1001110111 (512 xor 119)
1001111101 (512 xor 125)
1010000111 (512 xor 135)
1010010101 (512 xor 149)
1010100011 (512 xor 163)
1010100101 (512 xor 165)
1010101111 (512 xor 175)
1010110111 (512 xor 183)
1010111101 (512 xor 189)
1011001111 (512 xor 207)
1011010001 (512 xor 209)
1011011011 (512 xor 219)
1011110101 (512 xor 245)
1011111001 (512 xor 249)
1100010011 (512 xor 275)
1100010101 (512 xor 277)
1100011111 (512 xor 287)
1100100011 (512 xor 291)
1100110001 (512 xor 305)
1100111011 (512 xor 315)
1101001111 (512 xor 335)
1101011011 (512 xor 347)
1101100001 (512 xor 353)
1101101011 (512 xor 363)
1101101101 (512 xor 365)
1101110011 (512 xor 371)
1101111111 (512 xor 383)
1110000101 (512 xor 389)
1110001111 (512 xor 399)
1110110101 (512 xor 437)
1110111001 (512 xor 441)
1111000111 (512 xor 455)
1111001011 (512 xor 459)
1111001101 (512 xor 461)
1111010101 (512 xor 469)
1111011001 (512 xor 473)
1111100011 (512 xor 483)
1111101001 (512 xor 489)
1111111011 (512 xor 507)

N=8の場合の結果:
8 次原始多項式:
100011101 (256 xor 29)
100101011 (256 xor 43)
100101101 (256 xor 45)
101001101 (256 xor 77)
101011111 (256 xor 95)
101100011 (256 xor 99)
101100101 (256 xor 101)
101101001 (256 xor 105)
101110001 (256 xor 113)
110000111 (256 xor 135)
110001101 (256 xor 141)
110101001 (256 xor 169)
111000011 (256 xor 195)
111001111 (256 xor 207)
111100111 (256 xor 231)
111110101 (256 xor 245)
    • good
    • 0

素数体2上の原始多項式を求めるプログラムをphpで作ってみたのですが


作る過程でプログラムを作るのに都合のよい条件は既に述べたものではなく
次の方がプログラム作成上いいという結論に達しました。

素数体2上のN次原始多項式f(x)の条件:
(1) x^(2^N-1)≡1 (mod f(x)) であること
(2) 0<n<2^N-1 なる整数nにおいて x^n≡1 (mod f(x)) でないこと

この条件だと既約多項式である必要がないのでプログラミングが楽でした。

プログラムはPHPで作成しました。
なお、結果の原始多項式は左詰めで
高次から低次に向かって各次数の係数のみを並べて
1行1原始多項式で表示しました。

<?php
$N=8;
$c=pow(2,$N);
for($p=1;$p<$c;$p++)
{
$f=$c^$p;
$a=1;
for($i=1;$i<$c;$i++)
{
$a<<=1;
if(($a & $c)==$c)$a^=$f;
if($a==1)break;
}
if($i==($c-1))
{
$s=sprintf("%b (%d xor %d)",$f,$c,$p);
echo"{$s}<br/>";
}
}
?>

結果:
1000010001 (512 xor 17)
1000011011 (512 xor 27)
1000100001 (512 xor 33)
1000101101 (512 xor 45)
1000110011 (512 xor 51)
1001011001 (512 xor 89)
1001011111 (512 xor 95)
1001101001 (512 xor 105)
1001101111 (512 xor 111)
1001110111 (512 xor 119)
1001111101 (512 xor 125)
1010000111 (512 xor 135)
1010010101 (512 xor 149)
1010100011 (512 xor 163)
1010100101 (512 xor 165)
1010101111 (512 xor 175)
1010110111 (512 xor 183)
1010111101 (512 xor 189)
1011001111 (512 xor 207)
1011010001 (512 xor 209)
1011011011 (512 xor 219)
1011110101 (512 xor 245)
1011111001 (512 xor 249)
1100010011 (512 xor 275)
1100010101 (512 xor 277)
1100011111 (512 xor 287)
1100100011 (512 xor 291)
1100110001 (512 xor 305)
1100111011 (512 xor 315)
1101001111 (512 xor 335)
1101011011 (512 xor 347)
1101100001 (512 xor 353)
1101101011 (512 xor 363)
1101101101 (512 xor 365)
1101110011 (512 xor 371)
1101111111 (512 xor 383)
1110000101 (512 xor 389)
1110001111 (512 xor 399)
1110110101 (512 xor 437)
1110111001 (512 xor 441)
1111000111 (512 xor 455)
1111001011 (512 xor 459)
1111001101 (512 xor 461)
1111010101 (512 xor 469)
1111011001 (512 xor 473)
1111100011 (512 xor 483)
1111101001 (512 xor 489)
1111111011 (512 xor 507)
    • good
    • 0

間違いではないのですがゴミがついています。


1,7,73の約数→1,7,73
直さなくてもたまたま間違いではないですがゴミがあると分かりにくいので削除すべきだと思いました。

位数2素数体係数多項式を位数2素数体係数n次既約多項式g(x)で割った余りが同一のものを同一視するという位数2素数体係数多項式の集合を考えるとそれは位数2^nの有限体(ガロア体GF(2^n))になる。
そしてGF(2^n)-{0}は乗法について有限群になる。
前記有限体上においてxのべき乗からなる巡回群GはGF(2^n)-{0}の部分群なのでその位数はGF(2^n)-{0}の位数2^n-1の約数である。
もしg(x)が原始多項式でないならばGの位数は2^n-1未満であって2^n-1の約数である。
従ってGの位数が2^n-1未満の2^n-1の約数でなければGの位数はg(x)は2^n-1であり原始多項式ということになる。

n=9の場合:
「2^9-1未満の2^9-1の約数」は1,7,73なのでGの位数が1,7,73の約数でなければg(x)は原始多項式ということになる。
x^1をg(x)で割った余りが1でなく(これは当たり前なので不要)
x^7をg(x)で割った余りが1でなく(これは当たり前なので不要)
x^73をg(x)で割った余りが1でない
ならばGの位数は2^9-1=511ということになりg(x)は原始多項式ということになる。
(2^9-1=511=7x73)

従ってNo1,No2,No3,No4は間違いで原始多項式の条件は

9次多項式f(x)が原始多項式である条件:
(1)既約多項式であること。
(2)x^73をf(x)で割った余りが1でないこと。
    • good
    • 0
この回答へのお礼

ご回答ありがとうございます。

専門用語でけっこうわからないところがあるので、
とりあえず一つずつ解決していこうと思います!

また質問するかもしれないです(^0^;

お礼日時:2009/08/01 15:01

またまた間違いが有ったので修正(n-1とnの取り違えと他にも)




多項式をn次既約多項式g(x)で割った余りが同一のものを同一視するという多項式の集合を考えるとそれは位数2^nの有限体(ガロア体GF(2^n))になる。
そしてGF(2^n)-{0}は乗法について有限群になる。
前記有限体上においてxのべき乗からなる巡回群GはGF(2^n)-{0}の部分群なのでその位数はGF(2^n)-{0}の位数2^n-1の約数である。
もしg(x)が原始多項式でないならばGの位数は2^n-1未満であって2^n-1の約数である。
従ってGの位数が2^n-1未満の2^n-1の約数でなければGの位数はg(x)は2^n-1であり原始多項式ということになる。

n=9の場合:
「2^9-1未満の2^9-1の約数」は1,7,73なのでGの位数が1,7,73の約数でなければg(x)は原始多項式ということになる。
x^1をg(x)で割った余りが1でなく(これは当たり前なので不要)
x^7をg(x)で割った余りが1でなく(これは当たり前なので不要)
x^73をg(x)で割った余りが1でない
ならばGの位数は2^9-1=511ということになりg(x)は原始多項式ということになる。
(2^9-1=511=7x73)

従ってNo1,No2,No3,No4は間違いで原始多項式の条件は

9次多項式f(x)が原始多項式である条件:
(1)既約多項式であること。
(2)x^73をf(x)で割った余りが1でないこと。

でした。
いいわけとしては簡単な問題なので余り考えずに回答してしまいました。
教訓としては簡単な問題であってもよく考えるべきだとこうことです。
    • good
    • 0

間違いが有ったので修正




多項式をn-1次既約多項式g(x)で割った余りが同一のものを同一視するという多項式の集合を考えるとそれは位数2^nの有限体(ガロア体GF(2^n))になる。
そしてGF(2^n)-{0}は乗法について有限群になる。
xのべき乗で生成される巡回群GはGF(2^n)-{0}の部分群なのでその位数
はGF(2^n)-{0}の位数2^n-1を割り切る。
もしg(x)が原始多項式でないならばGの位数は2^n-1以外の2^n-1の約数である。
従ってGの位数が「2^n-1でない2^n-1の最大の約数」の約数でなければg(x)は原始多項式ということになる。

n=10の場合:
「2^10-1でない2^10-1の最大の約数」は341なのでGの位数が341の約数でなければg(x)は原始多項式ということになる。
x^341をg(x)で割った余りが1でないならばGの位数は341を越えることになり同時にGの位数は2^10-1の約数であるからGの位数は2^10-1=1023ということになりg(x)は原始多項式ということになる。


従ってNo1,No2,No3は間違いで原始多項式の条件は

9次多項式f(x)が原始多項式である条件:
(1)既約多項式であること。
(2)x^341をf(x)で割った余りが1でないこと。

でした。
    • good
    • 0

多項式をn-1次既約多項式g(x)で割った余りが同一のものを同一視するという多項式の集合を考えるとそれは位数2^nの有限体(ガロア体GF(2^n))になる。


そしてGF(2^n)-{0}は乗法について有限群になる。
xのべき乗で生成される巡回群GはGF(2^n)-{0}の部分群なのでその位数
はGF(2^n)-{0}の位数2^n-1を割り切る。
もしg(f)が原始多項式でないならばGの位数は2^n-1以外の2^n-1の約数である。
従ってGの位数が「√(2^n-1)を上回らない2^n-1の最大の約数」の約数でなければg(x)は原始多項式ということになる。

n=10の場合:
「√(2^10-1)を上回らない2^10-1の最大の約数」は31なのでGの位数が31の約数でなければg(x)は原始多項式ということになる。
x^31をg(x)で割った余りが1でないならばGの位数は√(2^10-1)を越えることになり同時にGの位数は2^10-1の約数であるからGの位数は2^10-1=1023ということになりg(x)は原始多項式ということになる。
    • good
    • 0

変換ミス:規約多項式→既約多項式



位数2の素数体を係数とする9次多項式f(x)が原始多項式である条件:
(1)f(x)が既約多項式であること。
(2)x^31をf(x)で割ったあまりが1でないこと。

解説:
(1)はいうまでもない。
(2)によって
1=x^0,x=x^1,x^2,x^3,x^4,...,x^(2^10-2)=x^1022
をf(x)で割った余りがすべて異なることが保証される。
    • good
    • 0
この回答へのお礼

ご回答ありがとうございます。

「(2)x^31をf(x)で割ったあまりが1でないこと。」
はなぜx^31なのでしょうか?どう意味があるのですか??

お礼日時:2009/07/30 20:14

位数2の素数体を係数とする9次多項式f(x)が原始多項式である条件:


(1)f(x)が規約多項式であること。
(2)x^31をf(x)で割ったあまりが1でないこと。

解説:
(1)はいうまでもない。
(2)によって
1=x^0,x=x^1,x^2,x^3,x^4,...,x^(2^10-2)
をf(x)で割った余りがすべて異なることが保証される。

注)2^10-1=3x11x31
    • good
    • 0

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

QM系列の生成多項式と原始多項式について

生成多項式や原始多項式に関する様々な投稿を見ましたが、
いまいち知りたいことがわからなかったので質問いたします。

周期 2^n - 1 のM系列を生成するには、{0,1}を体とする
n次の原始多項式を生成多項式として用いるということまでは
わかったのですが、このn次の原始多項式の求め方について、
いまいち理解できません。

例えば、周期 2^4 - 1 = 15のM系列を生成するには原始多項式

          x^4 + x^1 + 1 ー (1)

を用いるということですが、

            x^4 + x^2 + 1 ー (2)

ではM系列を生成できませんでした。
この2式の違いを理解していないことが原始多項式の求め方を
理解できない原因だと思うのですが、どなたかお詳しい方がいましたら、
ご教授お願いいたします。

Aベストアンサー

#1さんミスしてますので修正を。

x^4 + x^2 + 1 = (x^2 + x + 1)(x^2 - x + 1)
ですね。
念のため式変形を書くと、
x^4 + x^2 + 1 = x^4 + 2x^2 + 1 - x^2 = (x^2 + 1)^2 - x^2 = {(x^2 + 1) + x}{(x^2 + 1) - x}

だから、そもそも既約でないので、原始多項式にはなりません。
(原始多項式ならば、既約。逆は言えませんが)

しかし、単純に、原始多項式かどうかのチェックをしても、分かりますよね。

いま、数・係数としては、2で割った余りの世界(0と1からなる四則の出来る世界。色んな呼び名があるが、ここではF2と呼びます)を考えていますよね。

x^4 + x^2 + 1 でF2上の(つまり、係数が0と1からなる)多項式を割った「余り」を考えるとき、全ての多項式は、余りは3次以下の(係数が0と1からなる)式になりますよね。

係数が0と1であることから、ax^3 + bx^2 + cx + d たちは、全部で 2^4 = 16 個あるわけです。

いま、4次の原始多項式とは、xが、0を除く15個の余りを全て生成するような多項式を言います。

具体的に言うと、x , x^2 , x^3 , ・・ , x^15 を夫々割った余りがすべて異なり、0以外の全ての3次式が出てくるとき、原始多項式と言います。

ということは、もし途中で(余りとして)1がでたら、次から x , x^2 ・・と最初からの繰り返しになるので、駄目です。
よって x^15 の余りが1であり、それ以前に余り1が出てはいけません。

実は、この逆が言えて、
x , x^2 , x^3 , ・・ , x^14 の余りがすべて1でないとき(つまり x^15 ではじめて1になるとき)、(4次の)原始多項式である ・・・★

ことが言えます。

なので、(もっと良いテクニックは色々あるでしょうが)、★を満たすかどうかを、まじめに計算すれば分かります。

いま x^4 + x^2 + 1 についてやってみると、
x^4 + x^2 + 1 で割った余りは、x^4 + x^2 + 1 = 0 として、x^4 = x^2 + 1 (注:いまF2(2で割った余りの世界)上で考えているから、-1=1) を代入して次数を下げてゆけば求まりますよね。

すると、
x
x^2
x^3
x^4 = x^2 + 1
x^5 = x(x^2 + 1) = x^3 + x
x^6 = x(x^3 + x) = x^4 + x^2 = x^2 + 1 + x^2 = 1
( 2 = 0 より、2x^2 = 0 )
となり、6乗で1になってしまうので、 x^4 + x^2 + 1 は原始多項式でないと分かりますネ。

#1さんミスしてますので修正を。

x^4 + x^2 + 1 = (x^2 + x + 1)(x^2 - x + 1)
ですね。
念のため式変形を書くと、
x^4 + x^2 + 1 = x^4 + 2x^2 + 1 - x^2 = (x^2 + 1)^2 - x^2 = {(x^2 + 1) + x}{(x^2 + 1) - x}

だから、そもそも既約でないので、原始多項式にはなりません。
(原始多項式ならば、既約。逆は言えませんが)

しかし、単純に、原始多項式かどうかのチェックをしても、分かりますよね。

いま、数・係数としては、2で割った余りの世界(0と1からなる四則の出来る世界。色んな呼...続きを読む

Qガロア体の逆元計算について

私は今、AES暗号の勉強をしているのですが、ガロア体の所でつまづいています。

ガロア理論での逆元はx∈GF(p)のとき、
GF(p)でx * y が1になる時のyがxの逆元だと思うのですが、
下記のページの上から1/6ぐらいの場所にある逆数変換テーブルを見る限り、
この方法では求められないような気がします。

このページでは16進数の53の逆元を計算しているので、10進数では83になります。
(83 * 219 - 1 )/256= 0なので、53の逆元は219かなと思ったのですが、
以下のページでは16進数のCAで、10進数では202になってしまいます。

私は、どこで間違っているのか、指摘していただけないでしょうか。

http://bw-www.ie.u-ryukyu.ac.jp/~wada/design04/spec_j.html

Aベストアンサー

ガロア体を勉強しましょう
むちゃくちゃなことをしていますぞ

GF(2^8)の元を2つかける時に
それらの元をそれぞれ十進数にして整数の掛け算をしてはいけません

aとbをかけるには
aの多項式表現を作り
bの多項式表現を作り
それら多項式を多項式として掛け算し
参考のページにのっている既約多項式でその結果を割った余りを求め
その余り多項式の係数を並べて16進表現をだすのである
a逆元をもとめるには
aに0を除く255個の元すべてを上の方法でかけてみて1(上の意味で0x01)になるものを選べばいいのです

Q原始多項式の証明

原始多項式の証明
すみませんこの問題がどうしてもわかりません。だれか教えていただけないでしょうか?

x^4+x+1(この式はFp[x]に含まれる、p=2)はFp上の4次原始多項式であることを示せ。

まず、既約多項式であることを証明して、原始多項式であることを証明するのだと思うのですが・・・
どうかお願いします。

Aベストアンサー

取り敢えず証明するべきものが何なのかが分かっていないと
幾ら答えを教えても理解できるはずが無いと思いますので、
まずは「原始多項式」の定義を確認してから補足にでも
書いてください。

どのでこの問題が出たのか分かりませんが、この問題が
書かれているものに(本とか授業とか)定義も書いてあると
思いますが。

Q最小多項式

GF(2^4)の原始元αの最小多項式m1(x)=x^4+x+1とする。
m1(α)=0から、GF(2^4)の元をαのべき表現で表示できました。
ここで、すべての元において最小多項式を求めたいのですが。
講義ノートによると「最小多項式とは、その元を根とする次数最小の多項式」と書いてありました。
そうならば、α^3の最小多項式は(x-α^3)のはず、しかし、
ここで、α^6とα^12を導入し、α^3の最小多項式が
m3(x)=(x-α^3)(x-α^6)(x-α^12)
となるらしいです。また、一般的にAをf(x)=0の根とすると、A^{2*i}もまた、f(x)=0の根であることは知っているのですが、
なぜ最高次数を3にする必要があったのでしょうか?
最高次数が3以外じゃだめなんですか。例えば(x-α^3)(x-α^6)のように。
また、数の候補としてはα^3、α^6、α^12だけでなく、α^18、α^24、、、、、、、
膨大に候補があがると思います。α^3の最小多項式を考えていますが、
ほぼ無限に候補があがるため、これで、すべての元をあらわしてしまいそうなんですが…
こうなると、もはやα^3のペアとして、α^6とα^12のみならず、
どんな元でもよいと言うことにならないのでしょうか?
もし、ならないのであれば任意の元をかんがえて最小多項式を作ろうとしても、
このような事態は起きないのか?
わからないので是非教えてください。お願いします。

GF(2^4)の原始元αの最小多項式m1(x)=x^4+x+1とする。
m1(α)=0から、GF(2^4)の元をαのべき表現で表示できました。
ここで、すべての元において最小多項式を求めたいのですが。
講義ノートによると「最小多項式とは、その元を根とする次数最小の多項式」と書いてありました。
そうならば、α^3の最小多項式は(x-α^3)のはず、しかし、
ここで、α^6とα^12を導入し、α^3の最小多項式が
m3(x)=(x-α^3)(x-α^6)(x-α^12)
となるらしいです。また、一般的にAをf(...続きを読む

Aベストアンサー

nを2以上整数としてGF(2^n)上の元αの最小多項式:
GF(2)上の元を係数とする多項式f(x)のうちf(α)=0となる次数最小のもの

f(x)をGF(2)上の元を係数とする多項式としたとき明らかに
(f(x))^2=f(x^2)
であるからもしαをGF(2^n)の元としたときf(α)=0ならば
f(α)=0,f(α^2)=0,f(α^4)=0,…,f(α^(2^k)=0,…

以下問題に戻る
GF(2)上の多項式f(x)をα^3の最小多項式とすると
f(α^3)=0,f(α^6)=0,f(α^12)=0,f(α^24=α^9)=0,f(α^48=α^3)=0
だから
f(x)はα^3,α^6,α^12,α^9を根に持つ
f(x)=(x-α^3)・(x-α^6)・(x-α^12)・(x-α^9)=x^4+x^3+x^2+x+1

Qガロア体

今友達が暗号化の勉強をしていて,ガロア体が分からないそうです.ぼくもよくわからないので,誰か分かりやすいHPを知っていたら教えてください.

Aベストアンサー

雑過ぎたので多少雑ですが修正します。

pを素数とすると
GF(p)は{0,1,2,・・・,p-1}
からなります。
掛け算は
x,y∈GF(p)とするとx・yをpで割った余り
逆元は
x∈GF(p)とするとx・yをpで割った余りが1になるyでありyをx^(-1)とかく
割り算は
x,y∈GF(p)とするとx・y^(-1)をpで割った余り
足し算は
x,y∈GF(p)とするとx+yをpで割った余り
引き算は
x,y∈GF(p)とするとx+p-yをpで割った余り
{0,1,2,・・・,p-1}に掛け算と足し算を以上のように定義すれば体になることは簡単に証明できます。

g(x)をGF(p)の元を係数とするn次既約多項式とすると
GF(p^n)はGF(p)の元を係数とするn次未満の多項式全体で表現されます。
GF(p)のときと同じようにpの代わりにg(x)を使って掛け算や足し算を定義すれば良いのです。
なおg(x)を原始多項式に選べば
多項式xのべき乗で0以外のすべてのGF(p^n)の元(p^n-1個しかない)を表現することができます。
以上はGF(p^n)の多項式表現ですが多項式の係数の並びで表現したものがGF(p^n)のベクトル表現です。

雑過ぎたので多少雑ですが修正します。

pを素数とすると
GF(p)は{0,1,2,・・・,p-1}
からなります。
掛け算は
x,y∈GF(p)とするとx・yをpで割った余り
逆元は
x∈GF(p)とするとx・yをpで割った余りが1になるyでありyをx^(-1)とかく
割り算は
x,y∈GF(p)とするとx・y^(-1)をpで割った余り
足し算は
x,y∈GF(p)とするとx+yをpで割った余り
引き算は
x,y∈GF(p)とするとx+p-yをpで割った余り
{0,1,2,・・・...続きを読む

Q法(mod)の四則演算について

とても困ってます。
情報セキュリティの課題で

・整数は素数を法とする演算では、四則演算が実行できる。その例を示せ。
・整数は合成数を法とする演算では、四則演算の一部で、解が一意に定まる場合と定まらない場合がある。その例を示せ。

この2つの問題が分かりません。
答えを教えていただけませんか?お願いします。

Aベストアンサー

以下、剰余算の計算式を「13 mod 7 = 6」(13÷7の余りが6という意味)のように表します。suryaさんの読みやすいように適宜読み替えて下さい。

・法が素数の場合
2つの整数(5, 13)を7で割ったときの剰余の四則演算の例を以下に示します。

1. 加算
13 mod 7 = 6, 5 mod 7 = 5なので、(13 mod 7) + (5 mod 7) = 11 mod 7 = 4 … (1)
また、(13 + 5) mod 7 = 18 mod 7 = 4 … (2)
(1)と(2)は同じ値になるので、(13 mod 7) + (5 mod 7) = (13 + 5) mod 7

2. 減算
13 mod 7 = 6, 5 mod 7 = 5なので、(13 mod 7) - (5 mod 7) = 1 mod 7 = 1 … (1)
また、(13 - 5) mod 7 = 8 mod 7 = 1 … (2)
(1)と(2)は同じ値になるので、(13 mod 7) - (5 mod 7) = (13 - 5) mod 7

3. 乗算
13 mod 7 = 6, 5 mod 7 = 5なので、(13 mod 7) × (5 mod 7) = 30 mod 7 = 2 … (1)
また、(13 × 5) mod 7 = 65 mod 7 = 2 … (2)
(1)と(2)は同じ値になるので、(13 mod 7) × (5 mod 7) = (13 × 5) mod 7

4. 除算
剰余の除算は整数や実数といった一般的な数値の除算と異なるので注意して下さい。
剰余での除算は「逆数を掛ける」ことで定義されます。「aをbで割る」はa×b^-1で表されます。

(3 mod 7) × (5 mod 7) = 1なので、(5 mod 7)^-1 = (3 mod 7)
また、3.乗算の結果から、(13 × 5^-1) mod 7 = (13 mod 7) × (5 mod 7)^-1が言える。これを計算すると、
(13 × 5^-1) mod 7 = (13 mod 7) × (5 mod 7)^-1 = (13 mod 7) × (3 mod 7) = 4


・法が合成数の場合
良い例かどうかは分かりませんが…。
法が8のときの除算を例に挙げてみます。

例えば、(5 mod 8) × (3 mod 8)^-1は(3 mod 8) × (3 mod 8) = 1だから、
(5 mod 8) × (3 mod 8)^-1 = (5 mod 8) × (3 mod 8) = 7のように計算できます。
しかし、(5 mod 8) × (4 mod 8)^-1は、4 mod 8の逆数を求めることができないため計算できません。

以下、剰余算の計算式を「13 mod 7 = 6」(13÷7の余りが6という意味)のように表します。suryaさんの読みやすいように適宜読み替えて下さい。

・法が素数の場合
2つの整数(5, 13)を7で割ったときの剰余の四則演算の例を以下に示します。

1. 加算
13 mod 7 = 6, 5 mod 7 = 5なので、(13 mod 7) + (5 mod 7) = 11 mod 7 = 4 … (1)
また、(13 + 5) mod 7 = 18 mod 7 = 4 … (2)
(1)と(2)は同じ値になるので、(13 mod 7) + (5 mod 7) = (13 + 5) mod 7

2. 減算
13 mod 7 = 6, 5 mod 7 = 5なので、(13 mod 7...続きを読む

Q巡回符号について

以下の問題についてお解りになる方、どうかご教授お願いします。
なるべく文章で表現したつもりですが、実際には図を見て回答するため、これだけではわからない!となるかもしれません。


問題

符号長7の二元巡回(7,4)の符号器を使用する。
この時、巡回符号の生成多項式を

g(x) = x^3 + x + 1

とする。



問題1
情報桁を表す多項式が x^2 + x +1  であるとき
符号器が出力する符号多項式はどのようなものか。

問題2
この巡回符号のパリティ検査行列を求めよ。

問題3
この巡回符号の符号語を送信したとき、
受信多項式 y(x) が x^5 + x^4 + x^3 + x^2 +1
であるとする。この受信多項式y(x)の誤りを訂正せよ。

Aベストアンサー

ネット上には巡回符号のことは書かれていますが
内容が難しく書かれているわりに実際に適用する方法が明快に書かれていない。問題だけで回答例がない。検査行列の作り方が書かれていない。
誤り訂正の例題が書かれていないので実際の誤り訂正の仕方が分からない。検査行列を求める前のg(x)で割り切れれば受信データは正しい(誤りなし)。割り切れなければ誤りありと判断する。という所まで書いてあって誤り訂正可能、しかしその仕方が書いてない。といった解説が多いですね。
今回のケースを考察してまとめると

検査行列H=
[1 0 1 1 1 0 0]
[1 1 0 1 0 1 0]
[0 1 1 1 0 0 1]

送信データX=[0111001]
2ビットのエラー発生して
受信データY=[0101101]
となった場合を考えると
誤りベクトルY・H~=[0 0 1]
これは検査行列Hの7列目に一致する。
誤りがない場合は誤りベクトルは[0 0 0]となるので誤りありと判定される。
受信データYに1ビットだけの誤りが含まれるなら
誤り訂正されたY'=[0101100]は正しい送信データとして判断してよい。
しかし2ビットの誤りが含まれている今回のケースでは
訂正された復号化されたデータY'[0101100]は正しい送信データと一致して
おらず正しく訂正されません。

つまり符号長7の二元巡回(7,4)符号のパリティチェックでは
誤りベクトルから判ることは次のことです。
■[0 0 0]→誤りなしで受信データは正しい。
■[0 0 0]以外→誤りあり、1ビットの誤りは訂正できる。2ビット以上の誤りは訂正できない。

ネット上には巡回符号のことは書かれていますが
内容が難しく書かれているわりに実際に適用する方法が明快に書かれていない。問題だけで回答例がない。検査行列の作り方が書かれていない。
誤り訂正の例題が書かれていないので実際の誤り訂正の仕方が分からない。検査行列を求める前のg(x)で割り切れれば受信データは正しい(誤りなし)。割り切れなければ誤りありと判断する。という所まで書いてあって誤り訂正可能、しかしその仕方が書いてない。といった解説が多いですね。
今回のケースを考察してまとめる...続きを読む

QシフトレジスタとXORを用いたM系列信号について

タイトル通り、シフトレジスタとXORを用いてM系列信号を出力しようとしています。
構成は下のサイトを参考にしています。
M系列乱数について「http://denshikosaku.web.fc2.com/other/Mrand.html」
画像は参考にしたサイトにあるシフトレジスタとXORの構成図です。
私もこの通りにしています。

しかし、クロックを掛けると出力電圧が0Vです。
オシロスコープにより波形を見てもM系列信号はでてきません。

手順は以下の通りにいています。

(1)VccとCLRに対し5Vの直流電圧を掛ける
(2)CKに対し振幅5V(0V~5V変化)、約1~10MHzの矩形波をかける
(3)出力される波形をオシロスコープで確認する

何か悪い点があったら指摘ください。詳しい方よろしくお願いします。

また別の方法でM系列信号(10Mbps)を生成できるものがあればそういった情報もいただければ幸いです。

Aベストアンサー

あぁ、そのサイトの回路図が間違ってますね。どこかで間違った回路図を見て真似したか、あるいは引き写す時に間違えたんでしょう。
電源をONした後に、74164の出力がすべて'0'だったとしてその後の動作を考えてみれば簡単に分かると思います。

サイトの情報・・特に個人が趣味でやっているようなところの情報というのは、もちろん正しいものもありますが、勘違いや大間違いという物が少なくありません。検索したら出てきた情報を何ら検証することなく、鵜呑みにすると今回のようにハマることになります。
サイトの情報は「間違っている可能性が高い」ということを大前提にして、自分でできる限り色々なところの情報とつき合わせたり、自分なりに動作を考えるなどして、きちんと裏を取っていく努力が必要ですよ。

Qハフマン符号のプログラム

 以下の問題に回答できる方,いらっしゃいましたらソースファイルと実行結果を送ってください。
 ファァイル(記号列)を読み込んで,ハフマン符号によりファイルを圧縮するプログラム(C言語)を作成する(プログラムは,圧縮を行うものと,解凍を行うものの2つ作る)。また,いくつか適当なファイルに対して,圧縮を行い圧縮率を測定する。
(1)圧縮プログラムについて
 圧縮のステップ
 (a)入力ファイルを読み込み各記号の出現頻度をカウントする。
 (b)得られた出現頻度を使って各符号のハフマン符号を生成する。
 (c)各符号の出現頻度を出力ファイルに書き出す。
 (d)もう一度入力ファイルを読み込みながら各符号をハフマン符号で置き換え    て出力ファイルに出力する。圧縮ファイルの形式は次のようになる。

  0x00の  0x01の … 0xffの 先頭文字の 2文字目の … 終端文字の
  出現頻度 出現頻度 出現頻度 符号語   符号語    符号語
   (c)で書きこむ部分      (d)で書きこむ部分

(2)解凍プログラムについて
 解凍のステップ
 (a)各符号の出現頻度を圧縮ファイルから読み込む。
 (b)得られた出現頻度を使って各符号のハフマン符号を生成する。
 (c)圧縮ファイルの符号語を読み込みながら各符号のハフマン符号と比較しも    し一致したらその記号を解凍ファイルに出力する。
 (d)(c)をファイルの終わりもしくは出現頻度をすべて足し合わせた記号数分処   理するまで繰り返す。
 関数について
 関数get_bit
 ファイルから1bit読み込んで戻り値として返す。
 (ファイルポインタはグローバル変数で用意する)

 関数put_bit
 引数として0,または1を渡すと1bitずつファイルに書き込む。
 (ファイルポインタはグローバル変数で用意する)

 以下の問題に回答できる方,いらっしゃいましたらソースファイルと実行結果を送ってください。
 ファァイル(記号列)を読み込んで,ハフマン符号によりファイルを圧縮するプログラム(C言語)を作成する(プログラムは,圧縮を行うものと,解凍を行うものの2つ作る)。また,いくつか適当なファイルに対して,圧縮を行い圧縮率を測定する。
(1)圧縮プログラムについて
 圧縮のステップ
 (a)入力ファイルを読み込み各記号の出現頻度をカウントする。
 (b)得られた出現頻度を使って各符号のハフ...続きを読む

Aベストアンサー

コンパイルが通る所迄は修正しましたが、分岐木の生成が正しく出来ていない感じがします。

この辺を、どの様に考えて作ろうとしているのか補足願えますか?
もしかしたら、私が考え方を間違って説明しているかも知れません。
生成されて来た分岐木データが、どうも単純にコードと対になって無い様子なのですが...。

取り合えず、現状のソースを張って置きます。
/* Quenista */
の入ってる行が、いじった所です。

/****************************************************

ハフマン符号

****************************************************/
#include <stdio.h>
#include <stdlib.h>
#include<string.h>/* Quenista*/

#define DEBUG
#define SIZE 256

/* 二分木 */
typedef struct _node {
unsigned int count; /* 頻度 */
int parent; /* 上の要素番号 */
int left; /* 左側を 0 */
int right; /* 右側を 1 */
} CODE;

CODE code[2*SIZE+1];
int mozi_count[SIZE];
int search_code; /* Quenista*/
int Hcode[SIZE][SIZE];
int hcode_count[SIZE]; /* ? */
int bit_count;
FILE *fp1,*fp2;

void put_bit(unsigned int bit);
void /*Quenista*/
main()
{
int i, total = 0;
char input_fname[] = "read.txt";
char output_fname[] = "out2.txt";

int min1, min2, freeNode, root;

#ifdef DEBUG
printf("a");/* Quenista Debug */
#endif
/* データの初期化 */
for( i = 0; i < 2*SIZE+1; i++ ) code[i].count = 0;
for( i = 0; i < SIZE; i++ ) mozi_count[i] = 0;
memset((char *)&hcode_count[0],0,sizeof(hcode_count));/* Quenista */

/* 文字頻度をカウント */
if((fp1 = fopen(input_fname,"r")) == NULL){
fprintf(stderr,"%s: can't opn file\n", input_fname);
exit(1);
}

while((i=fgetc(fp1)) !=EOF){
code[i].count++;
mozi_count[i]++;
total++;
}
fclose(fp1); /* Quenista(ファイルは、使わなくなった時点でクローズする方が良い) */

#ifdef DEBUG
printf("b");/* Quenista Debug */
#endif
/* ハフマン符号を生成する */

/* ハフマン木をつくる */
code[2*SIZE].count = 0x100; /* 番兵 */
for (freeNode = SIZE; ; freeNode++) {
min1 = min2 = 2*SIZE;
for (i = 2*SIZE-1; i >= 0; i--)
if (code[i].count > 0) {
if (code[i].count < code[min1].count) {
min2 = min1;
min1 = i;
} else if (code[i].count < code[min2].count)
min2 = i;
}
if (min2 == 513 - 1) break;
code[freeNode].count = code[min1].count + code[min2].count;
code[freeNode].left = min1;
code[freeNode].right = min2;

code[min1].parent = code[min2].parent = freeNode;
code[min1].count = code[min2].count = 0;
}
root = min1;

#ifdef DEBUG
for(i=0;i<512;i++){printf("[%3d:親%3d]\n",i,code[i].parent);} /* Quenist Debug */
#endif

for(i=0;i<256;i++){ /* コードの回数分のループを行う。 */
search_code=i; /* ←ここで、次に検索するコードを保存して置く */
while(code[search_code].parent<0x100&&code[search_code].parent!=0){ /* ←ここで、戻れなくなるまで探し続ける(親を訪ねて3千里。) *//* Quenista Offset加算 */
if(code[code[search_code].parent].left==search_code){ Hcode[i][hcode_count[i]]=0; } /* ここで、左に分岐しているのか調べ、左なら0 *//* Quenista Offset加算 */
else{ Hcode[i][hcode_count[i]]=1; } /* 右なら1を保存 */
search_code=code[search_code].parent; /* 一つ上に戻る *//* Quenista Offset加算 */
hcode_count[i]++; /* ビット数を、数えて置く */
}
}
/* (c) */
#ifdef DEBUG
printf("c");/* Quenista Debug */
#endif
if((fp2 = fopen(output_fname,"w")) == NULL){
fprintf(stderr,"%s: can't opn file\n", output_fname);
exit(1);
}
#ifdef DEBUG
fprintf(fp2,"Header:\n"); /*Quenista Debug */
#endif
for(i=0;i<SIZE;i++){
fprintf(fp2,"%d ", mozi_count[i]);
}
#ifdef DEBUG
fprintf(fp2,"\n"); /*Quenista Debug */
#endif
if((fp1 = fopen(input_fname,"r")) == NULL){ /* Quenista(再オープンが必要) */
fprintf(stderr,"%s: can't opn file\n", input_fname); /* Quenista */
exit(1); /* Quenista */
} /* Quenista */
#ifdef DEBUG
fprintf(fp2,"Data:\n"); /*Quenista Debug */
#ifdef endif
bit_count=0;
while(!feof(fp1)){/*Quenista*/
search_code=fgetc(fp1);/*Quenista*/
for(i=hcode_count[search_code];i>0;i--){ /*Quenista */
put_bit(Hcode[search_code][i-1]); /* Quenista*/
bit_count++;
}
}
#ifdef DEBUG
printf("d");/* Quenista Debug */
#endif
for(i=0;i<(7-(bit_count&0xF));i++) put_bit(0); /* Quenista */
fclose(fp1);
fclose(fp2);
}

void put_bit(unsigned int bit)
{
static unsigned int mask = 0x80;
static unsigned int byte = 0x00;

if(bit != 0){
byte = byte | mask;
}
mask = mask >> 1;

//8bit貯まったか
if(mask == 0x00){
if(fputc(byte,fp2) == EOF){
printf("Can't write \n");
exit(1);
}
mask = 0x80;
byte = 0x00;
}
}
/* end of file */

コンパイルが通る所迄は修正しましたが、分岐木の生成が正しく出来ていない感じがします。

この辺を、どの様に考えて作ろうとしているのか補足願えますか?
もしかしたら、私が考え方を間違って説明しているかも知れません。
生成されて来た分岐木データが、どうも単純にコードと対になって無い様子なのですが...。

取り合えず、現状のソースを張って置きます。
/* Quenista */
の入ってる行が、いじった所です。

/****************************************************

ハフマン符号

**...続きを読む

Qモジュロ2除算ってどうやるの?

情報処理の勉強をしてるのですが、CRCを算出する時の過程でモジュロ2除算というのを使うと書いてあります。

その中でこのように書かれているのですが、この計算の意味がわかりません。

X11+X10+X7 ÷ X6+X2+1 = X5+X4+1 余り…X5+X4+X2+1

モジュロ2除算って、どうやって計算するんですか?
教えて下さい。

Aベストアンサー

まずは予備知識から。
----------
例えば整数を3で割ると
「割り切れる」か「1余る」か「2余る」か、のいずれかです。
すなわち、余りは「0.1.2」以外にはありません。
それでは「-7」を3で割るとどうなるでしょうか?
(-7) ÷ 3 = (-2) 余り (-1)?
これは間違いとは言いにくいですが、
余りは「0,1,2」しか許されないとすれば
(-7) ÷ 3 = (-3) 余り 2
とするのが良いですね。
これは、数直線上に等間隔に整数をとって、
その下に余りを「0,1,2,0,1,2,……」と書いていき、
負の整数に対しても同様に延長すれば納得できます。
----------

ご質問の除算を、全く普通に行なえば
(x^11 + x^10 + x^7) ÷(x^6 + x^2 + 1)
= (x^5 + x^4 - 1) 余り (- x^5 - x^4 + x^2 + 1)
となります。これなら分かりますね。
ここで係数だけを取り出すと、
(1 1 0 0 1 0 0 0 0 0 0 0) ÷ (1 0 0 0 1 0 0)
= (1 1 0 0 0 -1) 余り (-1 -1 0 1 0 1)
となります。被除数(割られる数)と余りだけを対応させると、
(1 1 0 0 1 0 0 0 0 0 0 0) → (-1 -1 0 1 0 1)
すなわち、「110010000000」というデータがあったとき、
これらを係数に持つ多項式(x^11 + x^10 + x^7)を作り、
あらかじめ用意しておいた別の多項式(x^6 + x^2 + 1)で割った余りを計算し、
その係数を再びビット列に直して記録しておくわけです。
このとき、コンピュータは0か1しか格納できませんから、
これら以外の係数が現れたら偶数は0に、奇数は1に変換します。
これは言い換えれば、2で割った余り(modulo 2)を考えていることに相当します。
すなわち、上の例で得られた係数はさらに
(-1 -1 0 1 0 1) ≡ (1 1 0 1 0 1)と変換され、
ビット列「110101」が格納されます。
これを多項式に書き戻すと、
ご質問のような一見奇妙なmodulo除算ができあがります。

CRCでは、この余分な(= 冗長な)ビット列をチェックすることによって、
データ転送の誤りを検出するわけです。

まずは予備知識から。
----------
例えば整数を3で割ると
「割り切れる」か「1余る」か「2余る」か、のいずれかです。
すなわち、余りは「0.1.2」以外にはありません。
それでは「-7」を3で割るとどうなるでしょうか?
(-7) ÷ 3 = (-2) 余り (-1)?
これは間違いとは言いにくいですが、
余りは「0,1,2」しか許されないとすれば
(-7) ÷ 3 = (-3) 余り 2
とするのが良いですね。
これは、数直線上に等間隔に整数をとって、
その下に余りを「0,1,2,0,1,2,……」と書いていき、
負の整数に対しても同様に延...続きを読む


人気Q&Aランキング