In　the　standard　hidden　Markov　model,　the　current　state　depends　only　on　the　immediately　preceding　state,　but　has　nothing　to　do　with　the　immediately　preceding　observation.　This　paper　presents　a　new　type　of　hidden　Markov　models　in　which　the　current　state　depends　both　on　the　immediately　preceding　state　and　the　immediately　preceding　observation,　and　the　state　sequence　is　still　a　Markov　chain.　Several　new　algorithms　are　given　and　simulated　for　the　three　basic　problems　of　interest,　including　probability　evaluation,　optimal　state　sequence　and　parameter　estimation.　One　example　of　its　initial　applications　shows　that　the　new　model　may　outperform　the　standard　model　in　some　circumstance.　(c)　2004　Elsevier　B.V.　All　rights　reserved.